559
Dijkstra算法詳解
1.dijkstra算法簡介
Dijkstra算法是由E.W.Dijkstra於1959年提出，又叫迪傑斯特拉算法，它應用了貪心算法模式，是目前公認的最好的求解最短路徑的方法。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題，其主要特點是每次迭代時選擇的下一個頂點是標記點之外距離源點最近的頂點。但由於dijkstra算法主要計算從源點到其他所有點的最短路徑，所以算法的效率較低。
2.dijkstra算法基本過程
假設路網中每一個節點都有標號
是從出發點s到點t的最短路徑長度；
表示從s到t的最短路徑中t點的前一個點。求解從出發點s到點t的最短路徑算法的基本過程為：
1. 初始化。出發點設置為：
標記起源點s，記k = s,其他所有點設為未標記。
2. 檢驗從所有已標記的點k到其他直接連接的未標記的點j的距離，並設置:
3. 選取下一個點。從所有未標記的點中選取 最小的點i，點i被選為最短路徑中的一點，並設為已標記的。
4. 找到點i的前一點。從已經標記的點集合中找到直接連接到點i的點,並標記為 。
5. 標記點i。如果所有的點已標記，則算法結束。否則，記k = i，轉到2繼續。
從以上算法的步驟中可以看出 ：dijkstra算法的關鍵部分是從未標記的點中不斷地找出距離源點距離最近的點，並把改點加入到標記的點集合中，同時更新未標記的點集合中其餘點到起始點的最短估計距離[z1] 。
以一個帶有權值的無向圖為例，用dijkstra算法分析從源點A到目標點F的最短路徑。
1. 用帶有權值的一個矩陣w表示含有n各節點的帶權無向圖， 代表弧段 的權值，如果從節點 到節點 不連通，那麼 ，帶權值圖鄰接矩陣如下圖所示.設置A為源點,G為目的點, 代表從節點A到有向圖中其他節點 的最短路徑長度。設置初始值
代表標記的節點集合。
2. 
是從A點出發求出的一條最短路徑上的終止節點，令
；
3. 修改起始節點A到集合
之間的最短路徑的長度值，如果d(j)+w(j,k) < d(k)，那麼d(k) = d(j) + w(j,k)；
4. 重複步驟2、3的操作N-1次，最終得到從起始節點A到其他節點的最短路徑，按照遞增的順序排列路徑的長度。
3.dijkstra算法的流程圖如下所示：
最後更新：2017-04-03 16:49:04