5.3.4 附录 E 最短路径算法——Dijkstra 算法
在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即
Bellman-Ford 算法和 Dijkstra 算法。这两种算法的思路不同，但得出的结果是相同的。我
们在下面只介绍 Dijkstra 算法，它的已知条件是整个网络拓扑和各链路的长度。
应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之
间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。
下面以图 E-1 的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最
短路径。为方便起见，设源结点为结点 1。然后一步一步地寻找，每次找一个结点到源结
点的最短路径，直到把所有的点都找到为止。
图 E-1 求最短路径算法的网络举例
令 D(v)为源结点(记为结点 1)到某个结点 v 的距离，它就是从结点 1 沿某一路径到结点
v 的所有链路的长度之和。再令 l(i, j)为结点 i 至结点 j 之间的距离。整个算法只有以下两
个部分：
(1) 初始化
令 N 表示网络结点的集合。先令 N = {1}。对所有不在 N 中的结点 v，写出
在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，
可以使 D(v) = 99。
(2) 寻找一个不在 N 中的结点 w，其 D(w)值为最小。把 w 加入到 N 中。然后对所有不在
N 中的结点 v，用[D(v), D(w) + l(w, v)]中的较小的值去更新原有的 D(v)值，即：
D(v)←Min[D(v), D(w) + l(w, v)] (E-1)
(3) 重复步骤(2)，直到所有的网络结点都在 N 中为止。
表 E-1 是对图 E-1 的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了 5 次。
表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的 D(w) 值。当第 5 次执
行步骤(2)并得出了结果后，所有网络结点都已包含在 N 之中，整个算法即告结束。
表 E-1 计算图 E-1 的网络的最短路径
步骤
N D(2) D(3) D(4) D(5) D(6)
初始化 {1} 2 5 1
∞ ∞
1 {1, 4} 2
4
① 2 ∞
5.31
评论0