最短路問題-D算法課件

最短路問題

最短路問題

1一、問題的提法及應用背景

（1）問題的提法——尋求網絡中兩點間的最短路就是尋求連接這兩個點的邊的總權數(shù)最小的通路。（注意：在有向圖中，通路——開的初等鏈中所有的弧應是首尾相連的。）

（2）應用背景——管道鋪設、線路安排、廠區(qū)布局、設備更新等。一、問題的提法及應用背景（1）問題的提法——尋求網絡中兩點2二、最短路算法

1．

D氏標號法（Dijkstra）；邊權非負2.列表法（福德法）；有負權，無負回路4v1v2v3v4v6v5v722561413412二、最短路算法

1．D氏標號法（Dijkstra）；邊權非31．D氏標號法（Dijkstra）（1）求解思路——從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

（2）使用條件——網絡中所有的弧權均

非負，即。1．D氏標號法（Dijkstra）（2）使用條件——網絡中所4（3）選用符號的意義：

①

P

標號（Permanent固定/永久性標號）——從始點到該標號點的最短路權②

T

標號（Temporary臨時性標號）——從始點到該標號點的最短路權上界（3）選用符號的意義：5（4）

計算步驟及例子：第一步：給起始點v1標上固定標號,其余各點標臨時性標號T(vj)=,j1;=l1j第二步：考慮滿足如下條件的所有點①與v1相鄰的點，即;②具有T標號，即，

為T

標號點集.

修改的T標號為，并將結果仍記為T(vj)。svj?若網絡圖中已無滿足此條件的T標號點，停止計算。（4）

計算步驟及例子：第一步：給起始點v1標上固定標號6第三步：令,然后將的T標號改成P

標號，轉入第二步。此時，要注意將第二步中的改為。第三步：令7例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標號，給其余所有點T標號。（2）例一、用Dijkstra算法求下圖從v1到v6的8例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421（4）例一、用Dijkstra算法求下圖從v1到v6的9v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：v1v2v3v4v6v5352242421（5）（6）反向追10237184566134105275934682求從1到8的最短路徑237184566134105275934682求從1到8的11237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1}m12237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,413237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,214237184566134105275934682X={1,2,4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,215237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,216237184566134105275934682X={1,2,4,6,7}min{d23,d53,d58,d78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,217237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,21823718456613