簡介
狄克斯特拉算法由荷蘭計算機科學(xué)家艾茲赫爾·狄克斯特拉在1956年提出是一個解決的是有向圖中最短路徑問題，在狄克斯特拉算法中，給每段都分配了一個權(quán)重，狄克斯特拉算法找出總權(quán)重最小的路徑
狄克斯特拉算法的使用
思考
下圖是一個加權(quán)圖，數(shù)字代表權(quán)重
圖 0_1.png
為了方便理解我們可以把A點看成是家，F(xiàn)點看成是公司，權(quán)重看成花費的時間，那么如何才能找到從家到公司的耗時最短的路線呢？
使用
狄克斯特拉算法包含4個步驟
- 找出最優(yōu)節(jié)點，即距離當前節(jié)點權(quán)重值最小的節(jié)點
- 更新該節(jié)點的鄰居的開銷
- 重復(fù)這個過程，直接對圖中的每個節(jié)點都這樣做
- 計算最終路徑
以圖0_1為例，我們來看一下計算過程
找出最優(yōu)節(jié)點，并記錄下父節(jié)點，未知節(jié)點暫時認為是無窮大
第一步
| 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 | ∞ | ∞ | ∞ |
最優(yōu)節(jié)點為 B ,權(quán)重為 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 | ∞ |
最優(yōu)節(jié)點為 C ,權(quán)重為 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 |
最優(yōu)節(jié)點為 E ,權(quán)重為 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 節(jié)點的權(quán)重替換為 16
最優(yōu)節(jié)點為 D ,權(quán)重為 16
