dijkstra算法演示_dijkstra算法例題_longshengguoji的專欄
本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。
1.dijkstra算法簡介
Dijkstra算法是由E.W.Dijkstra于1959年提出，又叫迪杰斯特拉算法，它應(yīng)用了貪心算法模式，是目前公認(rèn)的最好的求解最短路徑的方法。算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題，其主要特點(diǎn)是每次迭代時(shí)選擇的下一個(gè)頂點(diǎn)是標(biāo)記點(diǎn)之外距離源點(diǎn)最近的頂點(diǎn)。但由于dijkstra算法主要計(jì)算從源點(diǎn)到其他所有點(diǎn)的最短路徑，所以算法的效率較低。
2.dijkstra算法基本過程假設(shè)路網(wǎng)中每一個(gè)節(jié)點(diǎn)都有標(biāo)號(hào)
1. 初始化。出發(fā)點(diǎn)設(shè)置為：
標(biāo)記起源點(diǎn)s，，記k = s,其他所有點(diǎn)設(shè)為未標(biāo)記。
2. 檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其他直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置:
3. 選取下一個(gè)點(diǎn)。從所有未標(biāo)記的點(diǎn)中選取 最小的點(diǎn)i，點(diǎn)i被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。
4. 找到點(diǎn)i的前一點(diǎn)。從已經(jīng)標(biāo)記的點(diǎn)集合中找到直接連接到點(diǎn)i的點(diǎn),并標(biāo)記為 。
5. 標(biāo)記點(diǎn)i。如果所有的點(diǎn)已標(biāo)記，則算法結(jié)束。否則，記k = i，轉(zhuǎn)到2繼續(xù)。
從以上算法的步驟中可以看出 ：dijkstra算法的關(guān)鍵部分是從未標(biāo)記的點(diǎn)中不斷地找出距離源點(diǎn)距離最近的點(diǎn)，并把改點(diǎn)加入到標(biāo)記的點(diǎn)集合中，同時(shí)更新未標(biāo)記的點(diǎn)集合中其余點(diǎn)到起始點(diǎn)的最短估計(jì)距離 。
以一個(gè)帶有權(quán)值的無向圖為例，用dijkstra算法分析從源點(diǎn)A到目標(biāo)點(diǎn)F的最短路徑。
1. 用帶有權(quán)值的一個(gè)矩陣w表示含有n各節(jié)點(diǎn)的帶權(quán)無向圖， 代表弧段 的權(quán)值，如果從節(jié)點(diǎn) 到節(jié)點(diǎn) 不連通，那么 ，帶權(quán)值圖鄰接矩陣如下圖所示.設(shè)置A為源點(diǎn),G為目的點(diǎn), 代表從節(jié)點(diǎn)A到有向圖中其他節(jié)點(diǎn) 的最短路徑長度。設(shè)置初始值
2.
3. 修改起始節(jié)點(diǎn)A到集合
4. 重復(fù)步驟2、3的操作N-1次，最終得到從起始節(jié)點(diǎn)A到其他節(jié)點(diǎn)的最短路徑，按照遞增的順序排列路徑的長度。
3.dijkstra算法的流程圖如下所示：
本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。
本文編號(hào)：68704
本文鏈接：http://sikaile.net/wenshubaike/shangbiaozhuanli/68704.html
