最短路徑Dijkstra算法課件.ppt

《最短路徑Dijkstra算法課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、最短路徑Dijkstra算法1最短路徑兩點(diǎn)之間的最短路徑問題：求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑每一對(duì)頂點(diǎn)之間的最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:依最短路徑的長(zhǎng)度遞增的次序求得各條路徑源點(diǎn)v1v2…其中，從源點(diǎn)到頂點(diǎn)v的最短路徑是所有最短路徑中長(zhǎng)度最短者。2Dijkstra算法單源最短路徑問題是：給定帶權(quán)的有向圖G=（V，E），源點(diǎn)v∈V，求從v到V中其余各頂點(diǎn)的最短路徑。如何求解上圖中的最短路徑問題，Dijkstra提出了一種解決方案。即迪杰斯特拉算法，其基本思想如下：設(shè)置輔助數(shù)組Dist，其中每

2、個(gè)分量Dist[k]表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑的長(zhǎng)度。1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。V0和k之間存在弧V0和k之間不存在弧3）每次從集合V-S中取出具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u，將u加到S中，同時(shí)對(duì)數(shù)組Dist做必要的修改。若Dist[u]+G.arcs[u][k]

3、終點(diǎn),將Vk加入集合S中，而Dist[k]為最短路徑的長(zhǎng)度。4)重復(fù)操作2）、3）共n-1次。由此求得圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。若帶權(quán)圖G如下所示，根據(jù)上述算法來求解源點(diǎn)v0到v2的最短路徑。根據(jù)以上分析和舉例，不難得出狄杰斯特拉算法，其描述如下：VoidshortestPath(MGraphG,intV0,PathMatrix&P,ShortPathTable&D)//P[v]表示最短路徑，D[v]表示帶權(quán)長(zhǎng)度//P[v][w]為TRUE，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)//final

4、[v]為TRUE，即已經(jīng)求得從v0到v的最短路徑{for（v=0;v

5、i++){min=INFINITY;for(w=0;w