最短路问题DijkstraFloyd算法

最短路问题

赵嘉诚Dijkstra算法Ford算法Floyd算法SPFA算法一、什么是最短路问题例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，

v6，

v7，v8）费用3+2+10+2+4=21P3=……旅行路线总费用路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。即适用于DAG（有向无环图）v2v523464v3v1v4v6121061210v8v9v72363最短路问题严格的定义

给定有向网络D=（V(点)，A（弧），W（权）），任意弧aij∈A，有权w（

aij

）=wij，给定D中的两个顶点A，B。设P是D中从A到B的一条路，定义路P的权（长度）是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从vs到vt的路中，求一条路P0，使

称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。全局最短路径问题-求图中所有的最短路径。二、Dijkstra（迪杰特斯拉）算法

当所有

wij

≥0时，本算法是用来求给定点vs到任一个点vj最短路的公认的最好方法。事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

最短路的子路也是最短路。Dijkstra算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

思想：将D=（V，A，W）中vs到所有其它顶点的最短路按其路长从小到大排列为：u0≤u1≤u2≤…≤unu0表示vs到自身的长度，相应最短路记为：P0，P1，P2，…，Pn，取最小值的点为v1，∴P1=P（vs，v1）

假定u0，u1，…，uk的值已求出，对应的最短路分别为P1=P（vs，v1），P2=P（vs，v2），…，Pk=P（vs，vk）P1一定只有一条弧。

记则

使上式达到最小值的点v’可取为vk+1。

计算过程中可采用标号方法。Xk中的点，ui值是vs到vi的最短路长度，相应的点记“永久”标号；

XK中的点，ui值是vs到vi的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。前点标号

i:表示点vs到vj的最短路上vj的前一点。如

i=m，表示vs到vj的最短路上vj前一点是vm。6图上标号法:v5v223464v3v1v41210

61210v8v9v72363v60∞∞1∞∞∞36图上标号法:v5v223464v3v1v41210

61210v8v9v72363v60∞∞1∞∞∞36v5v223464v3v1v41210

61210v8v9v72363v60∞111∞∞∞3图上标号法:1,5v5v223464v3v1v41210

61210v8v9v72363v60∞111∞∞∞36图上标号法:1,5v5v223464v3v1v41210

61210v8v9v72363v60∞111∞∞∞35图上标号法:5v5v223464v3v1v41210

61210v8v9v72363v60∞111∞∞3∞图上标号法:5v5v223464v3v1v41210

61210v8v9v72363v60∞111∞∞36图上标号法:5v5v223464v3v1v41210

61210v8v9v72363v60111∞6∞3∞图上标号法:5v5v223464v3v1v41210

61210v8v9v72363v60101∞61239图上标号法:5v5v223464v3v1v41210

61210v8v9v72363v60101∞61239图上标号法:Dijkstra算法步骤：第1步：令us=0，uj=wsj

（1≤j≤n）若asjA，则第2步：(选永久标号)在XK中选一点vi，满足第3步：（给点vi永久性标号）第4步：(修改临时标号)对所有如果

令

j=i，uj=ui+wij否则,

i,,uj

不变,把k换成k+1，返回第2步。如果ui=+

，停止，令Xk+1=Xk∪﹛vi﹜,Xk+1=Xk＼﹛vi﹜令wsj=+,X0={vs},X0=V\X0,k=0,

i=0(0≤j≤n）从vs到XK中各点没有路；否则，转第3步。如果Xk+1=

，结束，到所有的点的最短路已经求得；否则，转第4步。例用Dijkstra算法求前面例子中从v1到各点的最短路。解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+

，

j=1（j=2，3，…，9）X0={v1}，X0={v2，v3，…，v9}v2v523464v3v1v4v6121061210v8v9v72363K=0∵min{u2，u3，u4，u5，u6，u7，u8，u9}=min{6，3，1，，，，，}=1=u4

∴点v4得永久标号，

4=1，X1={v1，v4}，

X1={v2，v3，

v5，v6

，v7，v8，v9}，在所有vj∈X1中，∵u6=

，u4+w46=1+10=11，即u4+w46<u6

∴修改临时标号u6=11

，

6=4，其余标号不变。v2v523464v3v1v4v6121061210v8v9v72363K=0+1=1∵min{u2，u3，u5，u6，u7，u8，u9}=min{6，3，，11，，，}=3=u3

∴点v3得永久标号，

3=1，X2={v1，v4，v3}，

X2={v2，

v5，v6

，v7，v8，v9}，

∵u2=6

，u3+w32=3+2=5，即u3+w32<u2∴修改临时标号u2=5

，

2=3，其余标号不变。在所有vj∈X2中，k=2+1=3∵min{u5，u6，u7，u8，u9}=min{6，11，，，}=6=u5

∴点v5得永久标号，

5=2，

X4={v1，v4，v3，v2，

v5}，X4={v6

，v7，v8，v9}，

∵u6=11

，u5+w56=6+4=10，即u5+w56<u6

u7=

，u5+w57=6+3=9，即u5+w57<u7

u8=

，u5+w58=6+6=12，即u5+w58<u8∴修改临时标号u6=10

，

6=5，u7=9，

7=5，

u8=12

，

8=5，在所有vj∈X4中，K=3+1=4∵min{u6，u7，u8，u9}=min{10，9，12，

}=9=u7

∴点v7得永久标号，

7=5，X2={v1，v4，v3，

v2，

v5，v7}，X2={v6

，v8，v9}，在vj∈X5中，临时标号不变。K=4+1=5∵min{u6，u8，u9}=min{10，12，

}=10=u6

∴点v6得永久标号，

6=5，X6={v1，v4，v3，

v2，

v5，v7

，v6}，X6={v8，v9}，点v8，v9临时标号不变。K=5+1=6∵min{u8，u9}=min{12，

}=12=u8

∴点v8得永久标号，

8=5，即从v1到v8的最短路长为u8=12，

∵

8=5，

5=2，

2=3，

3=1，

知从v1到v8的最短路为：

P1，8=P（v1，v3，

v2，

v5，v8）v2v523464v3v1v4v6121061210v8v9v72363问题：①本例中，v1到v9的最短路？②无向网络:③负权弧时。wijvivjwijwijvjvi无向网络中，最短路→最短链。④多个点对之间最短路？v1v2v312-3Dijkstra算法失效voidinit(){inti,j;for(i=1;i<=n;i++)//i==j的时候也可以初始化为0，只是有时候不合适for(j=1;j<=n;j++)mapp[i][j]=inf;}voiddijk(intu){inti,j,mins,v;for(i=1;i<=n;i++){dist[i]=mapp[u][i];mark[i]=false;}mark[u]=true;dist[u]=0;

while(1){mins=inf;for(j=1;j<=n;j++)if(!mark[j]&&dist[j]<mins)mins=dist[j],v=j;if(mins==inf)break;mark[v]=true;for(j=1;j<=n;j++)if(!mark[j]&&dist[v]+mapp[v][j]<dist[j])dist[j]=dist[v]+mapp[v][j];

}}三、Floyd算法

网络G=（V，A，W），令D=(dij)n

n，表示G中vi到vj的最短路的长度。

考虑G中任意两点vi，vj，如将G中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络G0，记wij为弧（vi，vj）的权。

在G0中加入v1及G中与vi，vj，v1相关联的弧，得G1，G1中vi到vj的最短路长记为,则一定有vivjv1wij

再在D1中加入v2及D中与vi，vj，v1，

v2相关联的弧，得D2，D2中vi到vj的最短路长记为，则有

递推，D中n个点逐个加入子网络，终得D中vi到vj的最短路路长

如果计