最短路径算法——Dijkstra算法

时间:2024-03-23 19:20:26
  在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个,即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同,但得出的结果是相同的。  

  下面只介绍Dijkstra算法,它的已知条件是整个网络拓扑和各链路的长度。

  应注意到,若将已知的各链路长度改为链路时延或费用,这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此,求最短路径的算法具有普遍的应用价值。

下面以图1的网络为例来讨论这种算法,即寻找从源结点到网络中其他各结点的最短路径。为方便起见,设源结点为结点1。然后一步一步地寻找,每次找一个结点到源结点的最短路径,直到把所有的点都找到为止。

最短路径算法——Dijkstra算法

1 求最短路径算法的网络举例

    令D(v)为源结点(记为结点1)到某个结点v的距离,它就是从结点1沿某一路径到结点v的所有链路的长度之和。再令l(i, j)为结点i至结点j之间的距离。整个算法只有以下两个部分:

    (1) 初始化    令N表示网络结点的集合。先令N = {1}。对所有不在N中的结点v,写出

          最短路径算法——Dijkstra算法

在用计算机进行求解时,可以用一个比任何路径长度大得多的数值代替∞。对于上述例子,可以使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)]                       (1)

    (3) 重复步骤(2),直到所有的网络结点都在N中为止。

    1是对图1的网络进行求解的详细步骤。可以看出,上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D(w) 值。当第5次执行步骤(2)并得出了结果后,所有网络结点都已包含在N之中,整个算法即告结束。

1    计算图1的网络的最短路径

步骤

N

D(2)

D(3)

D(4)

D(5)

D(6)

初始化

{1}

2

5

1

1

{1, 4}

2

4

2

2

{1, 4, 5}

2

3

1

4

3

{1, 2, 4, 5}

3

1

2

4

4

{1, 2, 3, 4, 5}

2

1

2

4

5

{1, 2, 3, 4, 5, 6}

2

3

1

2

 

  现在我们对以上的最短路径树的找出过程进行一些解释。

  因为选择了结点1为源结点,因此一开始在集合N中只有结点1。结点1只和结点2, 34直接相连,因此在初始化时,在D(2),D(3)和D(4)下面就填入结点1到这些结点相应的距离,而在D(5)和D(6)下面填入∞。

  下面执行步骤1。在结点1以外的结点中,找出一个距结点1最近的结点w,这应当是w = 4,因为在D(2),D(3)和D(4)中,D(4) = 1,它的之值最小。于是将结点4加入到结点集合N中。这时,我们在步骤1这一行和D(4)这一列下面写入①,数字1表示结点4到结点1的距离,数字1的圆圈表示结点4在这个步骤加入到结点集合N中了。

  接着就要对所有不在集合N中的结点(即结点2, 3, 56)逐个执行(E-1)式。

  对于结点2,原来的D(2) = 2。现在D(w) + l(w, v) = D(4) + l(4, 2) = 1 + 2 = 3 > D(2)。因此结点2到结点1距离不变,仍为2

  对于结点3,原来的D(3) = 5。现在D(w) + l(w, v) = D(4) + l(4, 3) = 1 + 3 = 4 < D(3)。因此结点3到结点1的距离要更新,从5减小到4

  对于结点5,原来的D(5) = ∞。现在D(w) + l(w, v) = D(4) + l(4, 5) = 1 + 1 = 2 < D(5)。因此结点5到结点1的距离要更新,从∞减小到2

  对于结点6,现在到结点1的距离仍为∞。

  步骤1的计算到此就结束了。

  下面执行步骤2。在结点14以外的结点中,找出一个距结点1最近的结点w。现在有两个结点(结点25)到结点1的距离一样,都是2。我们选择结点5(当然也可以选择结点2,最后得出的结果还是一样的)。以后的详细步骤这里就省略了,读者可以自行完成剩下的步骤。

                          最短路径算法——Dijkstra算法

2  Dijkstra算法求出最短路径树的各个步骤和在结点1的路由表

  最后就得出以结点1为根的最短路径树。图2给出了各步骤执行后的结果。从最短路径树可清楚地找出从源结点(结点1)到网内任何一结点的最短路径。图2还给出了在结点1的路由表。此路由表指出对于发往某个目的结点的分组,从结点1发出后的下一跳结点(在算法中常称为“后继结点”)和距离。当然,像这样的路由表,在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点,重新执行算法,然后才能找出以这个结点为根的最短路径树和相应的路由表。