图最短路径-dijkstra算法

1基本图算法陈嘉庆第一页，共29页。最短路径问题第二页，共29页。单源最短路径

Single-SourceShortestPath问题:带权有向图G（E,V),找出从给定源顶点s到其它顶点v的权最小路径。

“最短路径”=最小权路径的权是路径上所有边的权之和。例：道路图:从华师中山附中到市政府的最短路径?第三页，共29页。若顶点序列{V0,V1,…,Vn}是从V0到Vn的最短路，则序列{V0,V1,…,Vn-1}必为从V0到Vn-1的最短路。贪心算法权非负的单源最短路径算法（Dijkstra）12345612653723892第四页，共29页。v5v4v01005601010v1v2v3205030图中从v0到其余各顶点之间的最短路径:v0到v1无

v0到v2(v0,v2)10v0到v3(v0,v4,

v3)50v0到v4(v0,v4)30v0到v5(v0,v4,

v3,v5)60单源最短路径第五页，共29页。基本思想：将图中所有顶点分成两组:S,V-S

一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。

S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。权非负的单源最短路径算法（Dijkstra）第六页，共29页。权非负的单源最短路径算法（Dijkstra）

初始时,S仅包含源v0,

特殊路径：

从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中

(2)从V-S中取出具有当前最短路径长度的顶点w加入S中。第七页，共29页。最短路径——Dijkstra算法实例812345612653723892例求下图中顶点1到其余各顶点的最短路径。10123∞∞∞8\5\10\36414\2512\(1)初始化:1到v,若有边,则path[v]=边;dist[i]=边的值(2)选出dist[i]为最小值,则path[i]为1到i的最短路径(3)修改经过i更近的路径(4)重复（2）（3）第八页，共29页。最短路径——Dijkstra算法描述方法如下：（其中：path[v]和dist[v]表示从v0到v的最短路径及其长度）（1）对v0以外的各顶点vi，若<v0,vi>存在，则将其作为v0到vi的（暂时的）最短路径存放到path[v]中，将其权值作为对应的路径长度存放到dist[v]中。（2）从未解顶点中选择一个dist值最小的顶点v，则当前的path[v]和dist[v]就是顶点v的最终解。（3）由于某些顶点经过v可能会使得从v0到该顶点的路径更近一些，因此，应修改这些顶点的路径及其长度的值。（4）重复（2）（3），直到所有顶点求解完毕。9136425第九页，共29页。最短路径——Dijkstra算法实例顶点pathdist12345610实例：123456126537238920123∞∞∞()(1,2)(1,3)()()()(1,3,2)85(1,3,4)(1,3,5)10(1,3,4,6)14(1,3,5,6)12第十页，共29页。Dijkstra算法：一般情况下，Dist[k]=<源点到顶点i的弧上的权值>

或者=<源点到其它顶点的路径长度>+<其它顶点到顶点i的弧上的权值>

设置辅助数组Dist，其中每个分量Dist[i]表示

当前所求得的从源点到其余各顶点i的最短路径的长度。第十一页，共29页。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[i]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][i]<Dist[i]则将Dist[i]改为Dist[u]+G.arcs[u][i]V0和i之间存在弧V0和i之间不存在弧其中的最小值即为最短路径的长度。第十二页，共29页。单源最短路径

Single-SourceShortestPathDijkstra的时间复杂度是O(N2)，它不能处理存在负边权的情况。算法描述：设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。

a)初始化：dis[v]=∞(v≠s);dis[s]=0;pre[s]=0;

b)For(i=1;i<=n;i++)1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。

2.u标记为已确定最短路径

3.For

与u相连的每个未确定最短路径的顶点v

if(dis[u]+w[u][v]

<

dis[v])

{dis[v]

=

dis[u]

+

w[u][v];

pre[v]

=

u;

}

c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。第十三页，共29页。算法分析&思想讲解：从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2。特殊地，我们认为起点1也是一个“中转点”）。显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2的最短路径后，才能求出从起点到5的最短路径）。换句话说，如果起点1到某一点V0的最短路径要经过中转点Vi，那么中转点Vi一定是先于V0被确定了最短路径的点。所有顶点对间的最短路径问题（Floyd算法）

All-PairsShortestpaths中转点终点最短路1101221、2331、2、3441、254123452471162求解顺序第十四页，共29页。算法分析&思想讲解：我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。所有顶点对间的最短路径问题（Floyd算法）

All-PairsShortestpaths中转点终点最短路1101221、2331、2、3441、254123452471162求解顺序第十五页，共29页。算法分析&思想讲解：Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis[u]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话，这将它作为vi的“更短路径”dis[vi]（此时还不确定是不是vi的最短路径）。就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。所有顶点对间的最短路径问题（Floyd算法）

All-PairsShortestpaths中转点终点最短路1101221、2331、2、3441、254123452471162求解顺序第十六页，共29页。单源最短路径

Single-SourceShortestPathDijkstra的时间复杂度是O(N2)，它不能处理存在负边权的情况。例如下图这个例子。2到3的边权值为-4，显然从起点1到3的最短路径是-2（1→2→3）但是dijskstra在第二轮循环开始时会找到当前dis[i]最小的点3，并标记它为白点。这时的dis[3]=1，然而1却不是从起点到点3的最短路径。因为3已被标记为白点，最短路径值dis[3]不会再被修改了，所以我们在边权存在负数的情况下得到了错误的答案！12345213-4562第十七页，共29页。Constmaxvalue=99999.0maxlength=100;TypeArr1=array[1..maxlength]ofinteger;Arr2=array[1..maxlength,1..maxlength]ofreal;Arr3=array[1..maxlength]ofreal;Varprev:Arr1;

c:Arr2;

dist:Arr3;

s:array[1..maxlength]ofbooleann:integer;{邻接矩阵，c[i,j]为权}{dist[i]当前从源到顶点i的最短特殊路径长度（仅经过S中点）}{到该顶点最短路径长度已知的顶点集S}权非负的单源最短路径算法（Dijkstra）第十八页，共29页。Procedureshortpaths(n,v:integer);{单源最短路径问题的Digkstra算法}Vari,j,u:integer;temp,newdist:real;beginfori:=1tondobegindist[i]:=c[v,i];s[i]:=false;if(dist[i]=maxvalue)thenprev[i]:=0elseprev[i]:=v;end;Dist[v]:=0;s[v]:=true;BCDA1043215Ex:runthealgorithm{v到i的当前最短路径长度}初始化权非负的单源最短路径算法（Dijkstra）{源v加入到S}{prev记录i当前最短路的前一个顶点}第十九页，共29页。Fori:=1ton-1dobegintemp:=maxvalue;u:=v;forj:=1tondoif((nots[j])and(dist[j]<temp))thenbegin

u:=j;temp:=dist[j];end;

s[u]:=true;Temp变量中保存的是什么值?从未加入S中的顶点中选取当前特殊距离最短的顶点加入S时间复杂度:O(n2)权非负的单源最短路径算法（Dijkstra）第二十页，共29页。Forj:=1tondoif((nots[j])and(c[u,j]<maxvalue))thenbegin

newdist:=dist[u]+c[u,j];if(newdist<dist[j])thenbegin

dist[j]:=newdist;prev[j]:=u;endendendend;u是新加入S的顶点,计算u的所有相邻顶点的特殊距离。若比原距离小，则用新距离代替，并让u做为最短路径上的点权非负的单源最短路径算法（Dijkstra）第二十一页，共29页。23411043215Ex:runthealgorithmSudist[2]dist[3]dist[4]1-105maxvalue

1,339561,3,448561,3,4,22856IfDist[u]+c[u,j]<dist[j]thenbegindist[j]=dist[u]+c[u,j]prev[j]=uEnd;

第二十二页，共29页。权非负的单源最短路径算法（Dijkstra）基于邻接表的算法（当图边数远小于|V|2时采用）Const

maxint=maxlongint;maxlength=1000Typepointer=^adjnode;//邻接表adjnode=recordv:integer;//顶点标号w:integer;//权next:pointer;//指向下一邻接点指针end;Arr1=array[1..maxlength]oflongint;Arr2=array[1..maxlength]ofinteger;Arr3=array[1..maxlength]ofpointer;Vardist:Arr1;//特殊距离prev:Arr2;//i的前一节点adj:Arr3;//邻接表from,tto,n,e:integer;//源，目标，节点数，边数第二十三页，共29页。FunctionDeleteMin:integer；//取当前负距离最大（正距离最小）的顶点Vari,k:integer;temp:longint;begink:=0;temp:=-maxint;fori:=1tondoif(dist[i]<0)and(dist[i]>temp)thenbegintemp:=dist[i];

k:=i;end;DeleteMin:=k;End;负距离最大，正距离则最小权非负的单源最短路径算法（Dijkstra）第二十四页，共29页。Functionshortpath(from,tto:integer):boolean；Vari,k:integer;p:pointer;empty:boolean;beginfori:=1tondobegindist[i]:=-maxint;prev[i]:=0;end;k:=from;//源点dist[k]:=0;//源点距离

empty:=false;

权非负的单源最短路径算法（Dijkstra）初始化当前距离为某一较小负整数,dist[i]<0表示i∈V-S

dist[i]>0表示i∈S,省略数组S

节点i加入S后，dist[i]=-dist[i],变为正距离。第二十五页，共29页。while(notempty)do{还有顶点未被加入S或未到目标顶点}Beginp:=adj[k];while(p<>nil)dobeginif(dist[p^.v]<0)and(dist[p^,v]<-(dsit[k]+P^.w))then