欢迎大家来到IT世界,在知识的湖畔探索吧!
从烟台到陇西最短路径问题解决
一 前言
最短路径不仅是运筹学这的问题，同时也是我们日常生活中需要关注的地方，比如我们需要从起点A地到终点B地，但其中有众多路径可以选择，有易有难，这就需要我们去寻找方法去解决。本文以下内容运用Dijkstra(迪杰斯特拉)算法，以寻求最短路径，尽可能节约成本。目前，Dijkstra算法是解决最短路径的简单方法之一。
二 问题介绍与提出
1 Dijkstra算法介绍
Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在复数边。
2相关介绍
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重
带权重的图称为加权图（在无向图中，每条边都是一个环。狄克斯特拉算法只适用于有向无环图）
3.算法思路
1. 指定一个节点，例如我们要计算 ‘V1’ 到其他节点的最短路径；
2. 先求出的最短路径的点以及相应的最短路径，以及其他未求出最短路径的点（以及V1到该点的路径，注意 如上图所示，V1->V3由于没有直接相连 初始时为∞ 其他同理，并且初始时A->A = 0；
3. 第二步为 V1->V4=454 V1->V2=622 注意此时V1->其他=无穷
4. 从V1->V4=454 V1->V2=622找出路径最短的点，开始下一步，此时选择V1->V4
5. 下一步从V4出发，此时可以到V3 V6 V5 V7各点，并在表中更新路径(Pv)
6．循环执行 4、5 两步骤（注意此时的出发点也要同时更新），直至遍历结束，得到V1 到其他节点的最短路径
用于解决赋权图的单源路径最短问题
第一步
|
V |
初始状态 |
V1出发 |
||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
0 |
+∞ |
0 |
0 |
622 |
V1 |
|
V3 |
0 |
+∞ |
0 |
0 |
+∞ |
0 |
|
V4 |
0 |
+∞ |
0 |
0 |
454 |
V1 |
|
V5 |
0 |
+∞ |
0 |
0 |
+∞ |
0 |
|
V6 |
0 |
+∞ |
0 |
0 |
+∞ |
0 |
|
V7 |
0 |
+∞ |
0 |
0 |
+∞ |
0 |
V1已知出发
更新V2和V4(没问题)
第二步
|
V |
V4出发 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
0 |
622 |
V1 |
0 |
622 |
V1 |
|
V3 |
0 |
+∞ |
0 |
0 |
454+210 |
V4 |
|
V4 |
0 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
0 |
+∞ |
0 |
0 |
454+905 |
V4 |
|
V6 |
0 |
+∞ |
0 |
0 |
454+1080 |
V4 |
|
V7 |
0 |
+∞ |
0 |
0 |
454+1382 |
V4 |
(没问题)
第三步
|
V |
V3出发 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
0 |
622 |
V1 |
1（注意） |
622 |
V1 |
|
V3 |
0 |
454+210 |
V4 |
1 |
454+210 |
V4 |
|
V4 |
1 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
0 |
454+905 |
V4 |
0 |
454+905 |
V4 |
|
V6 |
0 |
454+1080 |
V4 |
0 |
454+1080 |
V3 |
|
V7 |
0 |
454+1382 |
V4 |
0 |
454+1390 |
V4 |
V3已知，只能到v6：
V1-V4-v3-v6=454+210+1272=1936>1534=454+1080 所以在此节点更新为V3
第四步
|
V |
V2出发 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
0 |
622 |
V1 |
1 |
622 |
V1 |
|
V3 |
1 |
454+210 |
V4 |
1 |
454+210 |
V4 |
|
V4 |
1 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
0 |
454+905 |
V4 |
0 |
454+905 |
V4 |
|
V6 |
0 |
454+1080 |
V3 |
0 |
454+1080 |
V3 |
|
V7 |
0 |
454+1390 |
V4 |
0 |
454+1390 |
V4 |
V1-V4-V5=454+905<622+1314所以不用更新节点
第五步
|
V |
V5出发 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
1 |
622 |
V1 |
1 |
622 |
V1 |
|
V3 |
1 |
454+210 |
V4 |
1 |
454+210 |
V4 |
|
V4 |
1 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
0 |
454+905 |
V4 |
1 |
454+905 |
V4 |
|
V6 |
0 |
454+1080 |
V3 |
0 |
454+1080 |
V3 |
|
V7 |
0 |
454+1382 |
V4 |
0 |
454+1382 |
V4 |
V1-V4-V5-V7=454+905+484=1843>454+1382=1836所以不用更新节点
第六步
|
V |
V6出发 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
1 |
622 |
V1 |
1 |
622 |
V1 |
|
V3 |
1 |
454+210 |
V4 |
1 |
454+210 |
V4 |
|
V4 |
1 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
1 |
454+905 |
V4 |
1 |
454+905 |
V4 |
|
V6 |
0 |
454+1080 |
V3 |
1 |
454+1080 |
V4 |
|
V7 |
0 |
1836 |
V4 |
0 |
454+1382 |
V4 |
V1-V4-V6-V7=454+1080+318=1852>454+1382=1836 所以不用更新节点
第七步结束
|
V |
V7已知 |
|||||
|
Known |
Dv |
Pv |
Known |
Dv |
Pv |
|
|
V1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
V2 |
1 |
622 |
V1 |
1 |
622 |
V1 |
|
V3 |
1 |
454+210 |
V4 |
1 |
454+210 |
V4 |
|
V4 |
1 |
454 |
V1 |
1 |
454 |
V1 |
|
V5 |
1 |
454+905 |
V4 |
1 |
454+905 |
V4 |
|
V6 |
1 |
454+1080 |
V4 |
1 |
454+1080 |
V4 |
|
V7 |
0 |
454+1382 |
V4 |
1 |
454+1382 |
V4 |
根据最终表，从Start节点V1开始到End节点V7结束的最短路径是454+1382=1836，路径是START->V1->V4->V7->END
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/40845.html
