迪杰斯特拉算法
應用場景-最短路徑問題
看一個應用場景和問題:
- 戰(zhàn)爭時期，勝利鄉(xiāng)有7個村莊(A, B, C, D, E, F, G) 蹂风，現(xiàn)在有六個郵差，從G點出發(fā)，需要分別把郵件分別送到 A, B, C , D, E, F 六個村莊
- 各個村莊的距離用邊線表示(權) 丑勤，比如 A – B 距離 5公里
- 問：如何計算出G村莊到 其它各個村莊的最短距離?
- 如果從其它點出發(fā)到各個點的最短距離又是多少?
迪杰斯特拉(Dijkstra)算法介紹
迪杰斯特拉(Dijkstra)算法是典型最短路徑算法,用于計算一個結點到其他結點的最短舉例。它的主要特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想),直到擴展到終點為止吧趣。
迪杰斯特拉(Dijkstra)算法過程
設置觸發(fā)頂點為v,頂點集合V{v1,v2,vi...},v到V中各頂點的距離構成距離集合Dis,Dis{d1,d2,di...},Dis集合記錄著v到圖中各頂點的距離(到自身可以看作0,v到vi距離對應di)
- 從Dis中選擇值最小的di并移出Dis集合,同時移出V集合中對應的頂點vi,此時的v到vi即為最短路徑法竞。
- 更新Dis集合,更新規(guī)則為: 比較v到V集合中頂點的距離值,與v通過vi到V集合中頂點的距離值,保留值較小的一個(同時也應該更新頂點的前驅結點為vi,表明是通過vi到到達的)
- 重復執(zhí)行兩步驟,直到最短路徑頂點目標頂點即可結束
