Dijkstra
一.算法背景
Dijkstra 算法（中文名：迪杰斯特拉算法）是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
二.算法描述
💡算法思想
设 G=(V,E)是一个带权有向图，把图中顶点集合 V 分为两组，第一组为已求出最短路径的顶点集合（用 S 表示，初始时 S 中只有一个源点，以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了）,第二组为其余未确定最短路径的顶点集合（用 U 表示）,按最短路径的的递增次序依次把第二组中的顶点加入 S 中。在加入的过程中，总保持从源点 v 到 S 中各个顶点的最短路径长度不大于从源点 v 到 U 中任何路径的长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从 v 到此顶点的最短路径长度，U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前路径的最短长度。算法步骤 a.初始时，只包括源点，即 S = {v}，v 的距离为 0。U 包含除 v 以外的其他顶点，即：U ={其余顶点}，若 v 与 U 中顶点 u 有边，则(u,v)为正常权值，若 u 不是 v 的出边邻接点,则(u,v)权值 ∞;b…从 U 中选取一个距离 v 最小的顶点 k，把 k，加入 S 中（该选定的距离就是 v 到 k 的最短路径长度）。
c.以 k 为新考虑的中间点，修改 U 中各顶点的距离；若从源点 v 到顶点 u 的距离（经过顶点 k）比原来距离（不经过顶点 k）短，则修改顶点 u 的距离值，修改后的距离值的顶点 k 的距离加上边上的权。
d.重复步骤 b 和 c 直到所有顶点都包含在 S 中。
执行动画
三：时间复杂度
设图的边数为 m，顶点数为 n。
Dijkstra 算法最简单的实现方法是用一个数组来存储所有顶点的 dis[] 时间复杂度为 O(n^2)
对于边数少于 n^{2}的稀疏图来说，我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为{\displaystyle O((m+n)logn)}，斐波纳契堆能稍微提高一些性能，让算法运行时间达到{\displaystyle O(m+nlogn)}。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。
四.算法缺点
算法限制要求：无负权值无法求出任意两点路径（求任意两点 为 弗洛伊德算法(floyd)）
五.算法实例
给出一个无向图
用 Dijkstra 算法找出以 A 为起点的单源最短路径步骤如下：
六.代码实现
以下为 C，C++，Matlab 语言的代码作为示例
C 语言 例题：sdut 3562 Proxy (迪杰斯特拉+反向建树）
#include<stdio.h>#include<string.h>#define N 1002#define Min(a,b) a>b?b:a#define INF 1000000int dis[N],bj[N];int mp[N][N];int n;void djsk(int v){ int i,j,k,min; for(i=0;i<=n;i++) dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离 dis[v]=0;// v 代表起始节点 自己到自己为0 bj[v]=1;// 标记 已找到短路 for(i=0;i<=n;i++)// i 代表已经找到的最短路条数 { min=INF;k=0; for(j=0;j<=n;j++)//从未找到最短路径元素中找一个路径最短的 if(!bj[j]&&dis[j]<min)min=dis[j],k=j; bj[k]=1;// 标记 已找到短路 for(j=0;j<=n+1;j++)//用但前最短路节点更新未找到最短路的节点 if(!bj[j]&&dis[j]>(dis[k]+mp[k][j]))dis[j]=dis[k]+mp[k][j]; }}
复制代码
C 语言_优化（队列） 例题： sdut 3562 Proxy迪杰斯特拉+反向建树
#include<stdio.h>#include<string.h>#define N 1002#define Min(a,b) a>b?b:a#define INF 1000000int dis[N],s[2][N];int mp[N][N];int n;void djsk(int v){ int i,j,k,min,q=0,d=0,c=0; for(i=0;i<=n;i++) s[c][q++]=i,dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离 dis[v]=0;// v 代表起始节点 自己到自己为0 while(q)//没有未找到最短路的元素 { min=INF;k=-1; for(j=0;j<q;j++)//从未找到最短路径元素中找一个路径最短的 if(dis[s[c%2][j]]<min) { min=dis[s[c%2][j]]; if(k!=-1)s[(c+1)%2][d++]=k; k=s[c%2][j]; } else s[(c+1)%2][d++]=s[c%2][j]; if(q==d)break;//寻找无改变 则未联通 for(j=0;j<d;j++)//用但前最短路节点更新未找到最短路的节点 if(dis[s[(c+1)%2][j]]>(dis[k]+mp[k][s[(c+1)%2][j]]))dis[s[(c+1)%2][j]]=dis[k]+mp[k][s[(c+1)%2][j]]; c=(c+1)%2;q=d;d=0;//交换层次 }}
复制代码
C++语言
const int INT = 32767;const int MAX = 10;int dis[MAX];int path[MAX];int A[MAX][MAX];
void Dijk(int v){ bool S[MAX]; // 判断是否已存入该点到S集合中 int n=MAX; for(int i=1; i<=n; ++i) { dis[i] = A[v][i]; S[i] = false; // 初始化 path[i] = v; } dis[v] = 0; S[v] = true; for(int i=2; i<=n; i++){ int mindist = INT; int u = v; // 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!S[j]) && dis[j]<mindist) { u = j; // u保存当前邻接点中距离最小的点的号码 mindist = dis[j]; } S[u] = true; for(int j=1; j<=n; j++) if((!S[j]) && A[u][j]<INT) { if(dis[u] + A[u][j] < dis[j]) //在通过新加入的u点路径找到离v点更短的路径 { dis[j] = dis[u] + A[u][j]; //更新dist path[j] = u; //记录前驱顶点 } } }}
复制代码
Matlab 语言
%迪杰斯特拉（单源）% 最短距离 ，路径 距离矩阵 起始点 结束点 function [res,index] = Djsk(mp,stat,ends) n=size(mp,1); %初始化 bj=zeros(n,1); %标记初始化 dis=mp(stat,:); %各点最短路距离初始化 path=ones(n,1),path=path.*stat;%各点最短路路径初始化 dis(stat)=0;bj(stat)=1; for i=1:n min=Inf; k=1;%局部初始化 for j=1:n %从未找到最短路径点集合中找一个路径最短的点 if (bj(j)~=1)&&(dis(j)<min),min=dis(j);k=j;end end bj(k)=1;%标记已找到的点的最短路径 for j=1:n %用但前最短路节点更新未找到最短路的节点（同时更新各点路径的前一个点，即父节点） if (bj(j)~=1)&&(dis(j)>(dis(k)+mp(k,j))), dis(j)=dis(k)+mp(k,j);path(j)=k;end end end%对要求最短路径进行处理 tem=ends;index(1)=ends;i=2;while path(tem)~=stat index(i)=path(tem); tem=path(tem); i=i+1;endindex(i)=stat;index=index(length(index):-1:1);res=dis(ends);end
复制代码
评论