Loading...
墨滴

进击的土豆同学

2021/08/29  阅读:59  主题:默认主题

最短路径—迪杰斯特拉算法(Dijkstra)

最短路径算法——迪杰斯特拉算法(Dijkstra)

最短路径问题是在一个网络中求一条从出发点到目的点的最短路径。 这里会介绍求解有圈网络和无圈网络的2个算法:迪杰斯特拉算法(Dijkstra)、弗洛伊德算法(Floyd)Dijkstra算法可以求网络中从源点到任何一个节点的最短路径,而Floyd算法的应用更加广泛,可以求网络中任意两点之间的最短路径。

1迪杰斯特拉算法(Dijkstra)

1.1 各种定义

表示从源点到节点 的最短距离, (≥0)表示弧 的长度。 根据上述两个定义给出某一节点 的标号(标号--通过数据对某一节点进行表示):

用该式表示节点 中的 表示源点到节点 的最短距离, 表示节点 的“父节点”(来源节点)为 ,即节点 的上一个节点是节点 中的 表示源点到节点 的最短距离=源点到节点 的最短距离+弧 的长度。

在Dijkstra算法中存在两种节点 的标号:暂时的、永久的。对于某一节点,如果找不到更短的路径达到该节点,则此时该节点的标号为永久的,否则则为暂时的。

1.2 步骤

第0步:对源点(节点1)进行永久地标号[0, -]. 令 .

第1步

<1>计算节点 有边相连的每一个暂时节点 不是永久的) . 如果节点 已经被另一个节点 连接并表示为 ,并且$s_i + d_{ij}

<2> 如果所有节点都是永久的,那么停止。否则,从所有暂时标号的节点中选择具有最短距离的进行永久标号 。令 ,重复执行第 步。

2 栗子

下图网络中给出了城市1(节点1)和其他4个城市(节点2到节点5)之间可能的路线以及每条边的长度。求城市1到其他4个城市的最短路径。

迭代0:给节点1分配永久标号[0, -]. 迭代1:节点1可以直接到达节点2、3,如下表

迭代1标号表-1
节点
标号
标号的状态
1
[0,-]
永久的
2
[0+100,1]=[100,1]
暂时的
3
[0+30,1]=[30,1]
暂时的

表中有两个暂时标号[100,1]和[30,1],其中,节点3的距离较小 ,因此把节点3的标号的状态转变为永久的。如下表:

迭代1标号表-2
节点
标号
标号的状态
1
[0,-]
永久的
2
[0+100,1]=[100,1]
暂时的
3
[0+30,1]=[30,1]
永久的
迭代1
迭代1

迭代2:节点3可以直接到达节点4和节点5,因此各个节点的标号变为:

迭代2标号表-1
节点
标号
标号的状态
1
[0,-]
永久的
2
[0+100,1]=[100,1]
暂时的
3
[0+30,1]=[30,1]
永久的
4
[30+10,3]=[40,3]
暂时的
5
[30+60,3]=[90,3]
暂时的

表中有三个暂时标号[100,1]、[40,3]和[90,3],其中,节点4的距离较小 ,因此把节点4的标号的状态转变为永久的。

迭代2标号表-2
节点
标号
标号的状态
1
[0,-]
永久的
2
[0+100,1]=[100,1]
暂时的
3
[0+30,1]=[30,1]
永久的
4
[30+10,3]=[40,3]
永久的
5
[30+60,3]=[90,3]
暂时的
迭代2
迭代2

迭代3:节点4可以直接到达节点2和节点5,则此时发现通过路径1-3-4-2到达节点2比路径1-2更短,即[55,4]中的55<[100,1]中的100;而路径1-3-5和1-3-4-5长度一样,得到下表

迭代3标号表-1
节点
标号
标号的状态
1
[0,-]
永久的
2
[40+15,4]=[55,4]
暂时的
3
[0+30,1]=[30,1]
永久的
4
[30+10,3]=[40,3]
永久的
5
[90,3]或[40+50,4]=[90,4]
暂时的

此时,在暂时节点中,节点2的距离 最小,并且,又因为节点2只能到节点3,而节点3已经是永久标号,不能改变,因此把节点2标记为永久。此时唯一剩下的暂时节点5也只能永久标号。

迭代3标号表-2
节点
标号
标号的状态
1
[0,-]
永久的
2
[40+15,4]=[55,4]
永久的
3
[0+30,1]=[30,1]
永久的
4
[30+10,3]=[40,3]
永久的
5
[90,3]或[40+50,4]=[90,4]
永久的
迭代3
迭代3

最后按照每个节点标号进行回溯,找到节点1(源点)到其他节点的最短路径。如对于节点2,: 节点2→[55,4]→节点4→[40,3]→节点3→[30,1]→节点1,所求最短路径为1→3→4→2,距离为55.

这是迪杰斯特拉算法,在党耀国主编的《运筹学》中,其实表现形式更加简单,有兴趣的读者可以去看一下。

进击的土豆同学

2021/08/29  阅读:59  主题:默认主题

作者介绍

进击的土豆同学