狄克斯特拉算法
2018-04-12 本文已影响7人
孙成酱子说
简介
狄克斯特拉算法由荷兰计算机科学家艾兹赫尔·狄克斯特拉在1956年提出是一个解决的是有向图中最短路径问题，在狄克斯特拉算法中，给每段都分配了一个权重，狄克斯特拉算法找出总权重最小的路径
狄克斯特拉算法的使用
思考
下图是一个加权图，数字代表权重
图 0_1.png
为了方便理解我们可以把A点看成是家，F点看成是公司，权重看成花费的时间，那么如何才能找到从家到公司的耗时最短的路线呢？
使用
狄克斯特拉算法包含4个步骤
- 找出最优节点，即距离当前节点权重值最小的节点
- 更新该节点的邻居的开销
- 重复这个过程，直接对图中的每个节点都这样做
- 计算最终路径
以图0_1为例，我们来看一下计算过程
找出最优节点，并记录下父节点，未知节点暂时认为是无穷大
第一步
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
Dijkstra第1步.png
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
最优节点为 B ,权重为 3
第二步
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
| 第二步 | B | A/3 | A/7 | B/15 | B/12 | ∞ |
Dijkstra第2步.png
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
| 第二步 | B | A/3 | A/7 | B/15 | B/12 | ∞ |
最优节点为 C ,权重为 7
第三步
Dijkstra第3步.png
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
| 第二步 | B | A/3 | A/7 | B/15 | B/12 | ∞ |
| 第三步 | C | A/3 | A/7 | B/15 | B/12 | C/17 |
最优节点为 E ,权重为 12
第四步
Dijkstra第4步.png
| Base | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 第一步 | A | A/3 | A/7 | ∞ | ∞ | ∞ |
| 第二步 | B | A/3 | A/7 | B/15 | B/12 | ∞ |
| 第三步 | C | A/3 | A/7 | B/15 | B/12 | C/17 |
| 第四步 | E | A/3 | A/7 | B/15 | B/12 | E/16 |
E: 12+4 = 16 < F:17 < D: 15 + 3 = 18 所以 F 节点的权重替换为 16
最优节点为 D ,权重为 16
