資源描述：
《最短路徑和網(wǎng)絡(luò)最大流問題.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三節(jié)網(wǎng)絡(luò)最短路徑問題v1v2v3v4v5v6v7v8v9661021043264362231已知道路交通網(wǎng)絡(luò)如下圖，弧旁的數(shù)字表示通過這條道路所需要的時間?，F(xiàn)某人要從v1出發(fā)到v8，求使總出行時間最小的路線。一、引例1問題的目標？v1v2v3v4v5v6v7v8v9661021043264362231——尋求上述賦權(quán)有向圖D=（VE）中頂點V1至V8的一條路徑P，路徑P中所有邊權(quán)之和W(a)
2、a?P（總出行時間）最小。2基本概念1、網(wǎng)絡(luò)：賦權(quán)有向圖D=（V，E）；2、網(wǎng)絡(luò)最短路徑：（1）設(shè)P是網(wǎng)
3、絡(luò)D=（VE）中從頂點vs到頂點vt一條路徑，則稱W(P)=?W(a)
4、a?P為路徑P的權(quán)；（2）若P*為D=（VE）中從頂點vs到頂點vt的一條路徑,而且W(P*)=Min{W(P)
5、P為D中頂點vs到頂點vt的路徑}，則稱P*為D中從vs到vt的最短路徑。3廣探法w6w2vw5w8w4w1w3w9w7w11w104深探法w6w2vw5w8w4w1w3w9w7w11w105一、Dijkstra算法一、算法的適用范圍、主要功能和前提條件（一）適用范圍——非負賦權(quán)有向圖——設(shè)有向圖D=（V，E），任
6、意a?A,權(quán)W（a）?0；（二）主要功能——求D=（V，E）中頂點v1至各點vj的最短路徑Pj*及其長度W(Pj*)=d1j；6二、算法思想（一）最短路徑的基本性質(zhì)——最短路徑的子路也為最短路徑；設(shè)D中頂點v1至vj的最短路徑Pj*=v1…vk…vivj其中，Pi*=v1…vk…vi必為D中頂點v1至vi的最短路，而且，W(Pj*)>=W(Pi*)d1j>=d1i7（二）搜尋方法——頂點標號法（1）T標號概念與方法：——臨時性（Temporary)標號；（2）P標號概念與方法：——永久性（Perm
7、enent)標號；8三、算法步驟（1）給vs以P標號，P（vs）＝0，其余各點均給T標號，T（vi）＝+∞；（2）若vi點為剛得到P標號的點，考慮這樣的點vj(vi,vj)屬于E，且vj為T標號，對vj的T標號進行如下的更改：（3）比較所有具有T標號的點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部點均為P標號則停止。否則用代vi轉(zhuǎn)回（2）。9例1狄克斯特拉算法0??????8151012151131131011
