§7.6最短路径 „应用背景：交通咨询、导航„约定 有向图 设V＝{0,
1,…,n-1}，边上的权值非负（长度）„分类 ①单源最短路径：1个源点到其余顶点的最短路径②单目标最短路径：将各边反向，即为问题1③单点对间最短路径：可用①来解，但二者渐近时间相同④所有点对间最短路径：亦可用①来解，即每个顶点作为源点 调用①
1 §7.6.1单源最短路径问题 „观察100 1305010 220 100 4603 源点中间顶点终点
0 1
0 3 03
2 03,
2 4 长度 10305060 上表是按路径长度递增序产生的从源点到其余顶点的最短路径 0到4的路径：<0,4>,<0,3,4>,<0,1,2,4>,<0,3,2,4> 长度：100，90， 70，60 ¾规律：当按长度增序生成从源s到其它顶点的最短路径时，则当前正在生成的最短路径上除终点外，其余顶点的最短路径均已生成 ¾例子：当求0到2的最短路径时，则该路径<0,3,2>上顶点0,3的最短路 径在此前已生成
2 §7.6.1单源最短路径问题 „约定从源s到终点v的最短路径简称为v的最短路径，SP(v)s到v的最短路径长度简称为v的最短距离，SD(v)红点集S：最短距离已确定的顶点集合白点集V-S：最短距离尚未确定的顶点集合 „算法思想-Dijkstra（1972图灵奖得主）基于上述观察™初始化：仅已知源s的最短距离SD(s)=
0，故红点集S={s};™扩充红点集：算法的每一步均是在当前白点集中选一最短距离最小的白点来扩充红点集，以保证算法是按长度增序来产生各顶点的最短路径;™结束：当前白点集空或仅剩下最短距离为∞的白点为止。
注：若s到某白点的路径不存在，可假设该白点的最短路径是一条长度为∞的虚拟路径。

3 §7.6.1单源最短路径问题 „如何扩充红点集？∵白点k的最短路径上除终点外，其余顶点的最短路径均已生成，故它们均为红点∴设置向量D[0..n-1]，对每一个白点v∈V-
S，用D[v]记录从源点s到达v，且除v外中间不经过任何白点的“最短”路径长度。
初始时每个白点v的D[v]值是边上的权。
Note：从s到v的中间不经过其他白点的路径可能不止1条，但只需将其中最短的那条的长度记录在D[v]中。
D[v]=SD[v]？即D[v]是v最终的最短距离吗？不一定，因为s到v可能存在包含其它白点作为中间点的更短路径。
D[v]只是v当前估计的最短距离（简称估计距离），即：D[v]≥SD[v]™如何在当前白点集中选一最短距离最小的白点k来扩充红点集？
4 §7.6.1单源最短路径问题 „如何扩充红点集？ Th.7.6.1若k是白点集中估计距离最小的顶点，则k的估计距离就是最短距离。
即：若D[k]=min{D[i]：∀i∈V-S}，则D[k]=SD[k]Pf（反证法）设D[k]不是k的最短距离，则必存在一条路径P：spk，其长度 Length(p)其中P1中仅有x为白点，由D[x]定义知length[P1]≥D[x]，又因权为非负，故length[P2]≥
0，所以 length(P)=length(P1)+length(P2)≥D[x](式2) 由式1,2得：D[k]>length(P)≥D[x]，这与k是当前白点集中估计距离最小的顶点矛盾！k是最短距离最小的白点吗？定理保证了k加入红点集的正确性
5 §7.6.1单源最短路径问题 „如何调整白点集中白点的估计距离？由于新红点k可能导致剩余白点的估计距离变小，使之离源点更近，故需调整。
设∀j∈V-
S，若D[j]由于k加入红点集而变小，则新路径P必是sp1kp2j，且P1中只有红点，P2必是边，即：Length(p)=D[k]+w.证明：略™调整方法若length(P)
6 1 §7.6.1单源最短路径问题 „例子 1010
1 0 0100100 304 ∞
2 330 1010 1 50 602 00100 100304 330 1010 1 502 0030490 6020330 010010130 10 460 50220330 1001305010 220 100 4603 最短距离：红色估计距离：白色依次求出的最短距离为：1)D[0]=02)D[1]=10，调整顶点23)D[3]=30，调整顶点2，44)D[2]=50，调整顶点45)D[4]=60 ¾最短路径树：各顶点的最短路径（实线）总是一棵以源点为根的树，称之 为最短路径树。

7 §7.6.1单源最短路径问题 „如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。
因此，要记录最优解则须引入附加信息。
因为最优解是最短路径树，故只需增加一个向量P[0..n-1],用P[i]记录顶点的双亲，由双亲的唯一性知，顶点i的最短路径可从P[i]反复上溯至根（源点）即可求得最优解。
„算法实现 G[i][j]= ∞ if不是边 w()otherwise
8 §7.6.1单源最短路径问题 voidDijkstra(AdjMatrixG,DistanceD,PathP,ints){ //0≤s≤n-
1,若不是边，则G[i][j]=Infinity BooleanS[n]；//S是红点集。
S[i]为真表示j为红点，否则为白点for(i=0;i9 for(i=0;iS[j]&&D[j]S[j]&&D[j]>D[k]+G[k][j]){ D[j]=D[k]+G[k][j];//修改白点j的估计距离，使之离s更近 P[j]=k;//k是j的前驱 } }//endfor } 10 „算法执行过程源点s＝
3 循环i红点集SkD[0]D[1]D[2]D[3]D[4]P[0]P[1]P[2]P[3]P[4] 初始化{3} －∞∞20060-1-13-13
1 {3,2} 2∞∞20030-1-13-12
2 {3,2,4}4∞∞20030-1-13-12
3 同上 －白点集{0,1}中所有点的估 计距离为∞，退出循环 „时间：时间O(n2)„构造解 1001305010 220 100 460311 „构造解 输出路径及其长度voidPrintPath（PathP，DistanceD）{//路径是逆向的 inti，pre;for(i=0;i=-1){ printf(“,%d”,pre);pre=P[pre];//上溯找前驱}}}12
2 §7.6.2所有点对间的最短路径问题 „解法
一 以每一顶点为源点，调用DIjkstra算法，时间O(n3) „解法
二 Floyd（1978年图灵奖得主）算法更简洁，但是时间仍为O(n3)™假设：加权邻接矩阵C（n×n） 0C[i][j]=∞ ifi=jif不是边 w()otherwise ™思想：∀i,j∈
V，若∈
E，则从i到j有一条路径，长度为C[i][j]。
但它不一定是最短路径，因为可能存在一条从i到j中间包含其他顶点的 更短路径。
因此，必须依次考虑能否在i和j之间加入顶点0,1…,n-
1,而得 到更短的路径。
13 §7.6.2
所有点对间的最短路径问题 „Floyd算法的基本步骤 定义n×n的方阵序列D－
1,D0,…Dn－
1,™初始化：D－1＝
C D－1[i][j]＝边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。
™迭代：设Dk－1已求出，如何得到Dk（0≤k≤n－1）？Dk－1[i][j]表示从i到j的中间点不大于k－1的最短路径p：i…j，考虑将顶点k加入路径p得到顶点序列q：i…k…j， 若q不是路径或q是长度大于p长度的路径，则当前的最短路径仍是上一步结果：Dk[i][j]=Dk－1[i][j]；否则用q取代p作为从i到j的最短路径。
因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径，所以从i到j中间点不大于k的最短路径长度为： Dk[i][j]＝min{Dk－1[i][j],Dk－1[i][k]+Dk－1[k][j]}矩阵序列D－
1,D0,…Dn－1可在同1个矩阵上迭代求得，为什么？ 14 §7.6.2所有点对间的最短路径问题 „Floyd算法的基本步骤 ™解矩阵：Path[n][n]：记录路径构造在第k次跌代中，P[i][j]记录从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。
当算法结束时，可由Path[i][j]得到从i到j的最短路径，其方法是从顶点i开始反复找其后继，直至找到顶点j或确认i到j没有路径为止。
15 §7.6.2所有点对间的最短路径问题 „Floyd算法实现 voidFloyd(AdjMatrixD,AdjMatrixC,intPath[n][n]){ for(i=0;i=j){printf(“->%d”,next);//输出后继顶点next=Path[next][j];//继续找后继顶点 }//endwhileprintf(“%->%d”,j);//输出终点 }//endif }//endfor } 17
3