6 最短路径.PPT

§7.6 最短路径 应用背景：交通咨询、导航 约定 有向图 设V＝{0,1,…,n-1}，边上的权值非负（长度） 分类 ①单源最短路径：1个源点到其余顶点的最短路径 ②单目标最短路径：将各边反向，即为问题1 ③单点对间最短路径：可用①来解，但二者渐近时间相同 ④所有点对间最短路径：亦可用①来解，即每个顶点作为源点调用① §7.6.1 单源最短路径问题 观察 §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到某白点的路径不存在，可假设该白点的最短路径是一条长度为∞的虚拟路径。 §7.6.1 单源最短路径问题 如何扩充红点集？ ∵白点k的最短路径上除终点外，其余顶点的最短路径均已生成，故它们均为红点 ∴设置向量D[0..n-1]，对每一个白点v∈V-S，用D[v]记录从源点s到达v，且除v外中间不经过任何白点的“最短”路径长度。初始时每个白点v的D[v]值是边s,v上的权。 Note：从s到v的中间不经过其他白点的路径可能不止1条，但只需将其中最短的那条的长度记录在D[v]中。 D[v]=SD[v]？即D[v]是v最终的最短距离吗？不一定，因为s到v可能存在包含其它白点作为中间点的更短路径。 D[v]只是v当前估计的最短距离（简称估计距离），即：D[v]≥SD[v] 如何在当前白点集中选一最短距离最小的白点k来扩充红点集？ §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：s k，其长度 Length(p)D[k] (式1) 由D[k]定义知，P至少包含1个白点作为中间点，不妨设x是P上第1个白点，则P可分解为： s x， x k。其中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加入红点集的正确性 §7.6.1 单源最短路径问题 如何调整白点集中白点的估计距离？ 由于新红点k可能导致剩余白点的估计距离变小，使之离源点更近，故需调整。 设?j∈V-S，若D[j]由于k加入红点集而变小，则新路径P必是 s k j，且P1中只有红点，P2必是边k,j，即： Length(p)= D[k] + wk,j. 证明：略 调整方法 若length(P)D[j]，则用length(P)来修正D[j]。 §7.6.1 单源最短路径问题 例子 §7.6.1 单源最短路径问题 如何构造最优解 因为D向量只记录了最优解的值，但不能得到最优解。因此，要记录最优解则须引入附加信息。 因为最优解是最短路径树，故只需增加一个向量P[0..n-1],用P[i]记录顶点的双亲，由双亲的唯一性知，顶点i的最短路径可从P[i]反复上溯至根（源点）即可求得最优解。 算法实现 ∞ if i,j不是边 G[i][j]= w(i,j) otherwise §7.6.1 单源最短路径问题 void Dijkstra ( AdjMatrix G, Distance D, Path P, int s ){ //0≤s ≤n-1,若i,j不是边，则G[i][j]=Infinity Boolean S[n]；//S是红点集。S[i]为真表示