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