介紹加權(quán)圖——提高或降低某些邊的權(quán)重。
尋路
狄克斯特拉算法包含4個(gè)步驟议街。
(1) 找出“最便宜”的節(jié)點(diǎn)，即可在最短時(shí)間內(nèi)到達(dá)的節(jié)點(diǎn)璧榄。
(2) 更新該節(jié)點(diǎn)的鄰居的開銷特漩，其含義將稍后介紹吧雹。
(3) 重復(fù)這個(gè)過程，直到對(duì)圖中的每個(gè)節(jié)點(diǎn)都這樣做了涂身。
(4) 計(jì)算最終路徑雄卷。
尋路
第一步 ：找出最便宜的節(jié)點(diǎn)。你站在起點(diǎn)蛤售，不知道該前往節(jié)點(diǎn)A還是前往節(jié)點(diǎn)B丁鹉。前往這兩個(gè)節(jié)點(diǎn)都要多長(zhǎng)時(shí)間呢？前往節(jié)點(diǎn)A需要6分鐘悴能，而前往節(jié)點(diǎn)B需要2分鐘揣钦。至于前往其他節(jié)點(diǎn)，你還不知道需要多長(zhǎng)時(shí)間漠酿。
第二步 ：計(jì)算經(jīng)節(jié)點(diǎn)B前往其各個(gè)鄰居所需的時(shí)間冯凹。
第三步 ：重復(fù)！
權(quán)重 （weight）
權(quán)重
帶權(quán)重的圖稱為加權(quán)圖 （weighted graph）炒嘲，不帶權(quán)重的圖稱為非加權(quán)圖 （unweighted graph）宇姚。
要計(jì)算非加權(quán)圖中的最短路徑，可使用廣度優(yōu)先搜索 摸吠。要計(jì)算加權(quán)圖中的最短路徑空凸，可使用狄克斯特拉算法 。
