Dijkstra最短路算法的特点和适应范围 一种隐阶段的动态规划方法,而且是正向递推 每次迭代只有一个节点获得永久标记,若有两个或两个以上 节点的临时标记同时最小,可任选一个永久标记;总是从 个新的永久标记开始新一轮的临时标记,是一种深探法 被框住的永久标记T表示v到y的最短路,因此要求d≥20, 第k次迭代得到的永久标记,其最短路中最多有k条边,因 此最多有n-1次送代 可以应用于简单有向图和混合图,在临时标记时,所谓相邻 必须是箭头指向的节点;若第n-1次迭代后仍有节点的标记 为∞,则表明v到该节点无有向路径 如果只求v到v的最短路,则当v得到永久标记算法就结束 了;但算法复杂度是一样的 应用Djkr算法n-1次,可以求所有点间的最短路 到所有点的最短路也是一棵生成树,但不是最小生成树16
16 Dijkstra最短路算法的特点和适应范围 • 一种隐阶段的动态规划方法，而且是正向递推 • 每次迭代只有一个节点获得永久标记，若有两个或两个以上 节点的临时标记同时最小，可任选一个永久标记；总是从一 个新的永久标记开始新一轮的临时标记，是一种深探法 • 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij0， 第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因 此最多有n−1 次迭代 • 可以应用于简单有向图和混合图，在临时标记时，所谓相邻 必须是箭头指向的节点；若第 n−1 次迭代后仍有节点的标记 为 ，则表明 vs 到该节点无有向路径 • 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束 了；但算法复杂度是一样的 • 应用 Dijkstra 算法 n−1 次 ，可以求所有点间的最短路 • vs 到所有点的最短路也是一棵生成树，但不是最小生成树
632 Marshal- Floyd算法(1962) Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题 该算法是一种整体算法,一次求出所有点间的最短路 该算法不允许有负权值回路,但可以发现负权值回路 该算法基于基本的三角运算 定义对给定的点间初始距离矩阵{丹},令d1=∞,Vi。对一个 固定点j,运算 dik=min{ditn+lh},V;k≠,称为三角运 算。(注意,这里允许ik) 定理依次对产1,2,…,n执行三角运算,则k最终等于i到k 间最短路的长度。 U / k
17 6.3.2 Warshall-Floyd算法 (1962) • Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题 • 该算法是一种整体算法，一次求出所有点间的最短路 • 该算法不允许有负权值回路，但可以发现负权值回路 • 该算法基于基本的三角运算 定义 对给定的点间初始距离矩阵{dij}，令dii=， i。对一 个 固定点 j，运算 dik=min{dik, dij+djk}, i, k j , 称为 三角运 算。(注意，这里允许 i=k) 定理 依次对 j=1,2,…,n 执行三角运算，则 dik 最终等于 i 到 k 间最短路的长度。 k j i dij djk dik
632 Floyd- Warshall算法(1962) for i=l to n do di= 若网路中存在负回路,则计算 for all e0 中,某些d会小于0,此时应 forj=l to n do 中断算法 显然, Floyd算法要进行n(n for i=l to n do if if then 1)2次加法和比较 fork=1 to n do if k#i then·如何回溯找出任两点之间的最 begin 短路? 在 Floyd算法中设一伴随矩阵 dik=mindik, ditdik E={eth},ek记录了i到k最短 if didi+dik then eiki 路中最后一个中间节点 end 例1中1到7点的最短路是125-7 查伴随矩阵E的第一行 234567 10020 5 18
18 6.3.2 Floyd-Warshall 算法 (1962) for i=1 to n do dii=; for all eij=0; for j=1 to n do for i=1 to n do if ij then for k=1 to n do if kj then begin dik=min{dik, dij+djk}; if dik>dij+djk then eik=j end; 例 1 中 1 到 7 点的最短路是 1-2-5-7 查伴随矩阵 E 的第一行 1 2 3 4 5 6 7 1 0 0 2 0 2 5 5 • 若网路中存在负回路，则计算 中，某些 dii 会小于0，此时应 中断算法 • 显然，Floyd 算法要进行 n(n- 1)2 次加法和比较 • 如何回溯找出任两点之间的最 短路？ • 在Floyd 算法中设一伴随矩阵 E={eik}， eik 记录了 i 到 k 最短 路中最后一个中间节点