資源描述：
《最短路問(wèn)題__迪杰斯特拉算法課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、最短路問(wèn)題一、問(wèn)題的提法及應(yīng)用背景（1）問(wèn)題的提法——尋求網(wǎng)絡(luò)中兩點(diǎn)間的最短路就是尋求連接這兩個(gè)點(diǎn)的邊的總權(quán)數(shù)最小的通路。（注意：在有向圖中，通路——開(kāi)的初等鏈中所有的弧應(yīng)是首尾相連的。）（2）應(yīng)用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。二、最短路算法1．D氏標(biāo)號(hào)法（Dijkstra）；邊權(quán)非負(fù)2.列表法（福德法）；有負(fù)權(quán)，無(wú)負(fù)回路4v1v2v3v4v6v5v7225614134121．D氏標(biāo)號(hào)法（Dijkstra）（1）求解思路——從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是
2、最短的。（2）使用條件——網(wǎng)絡(luò)中所有的弧權(quán)均非負(fù)，即。（3）選用符號(hào)的意義：①P標(biāo)號(hào)（Permanent固定/永久性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)②T標(biāo)號(hào)（Temporary臨時(shí)性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)上界（4）?計(jì)算步驟及例子：第一步：給起始點(diǎn)v1標(biāo)上固定標(biāo)號(hào),其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào)T(vj)=?,j?1;=l1j第二步：考慮滿足如下條件的所有點(diǎn)①與v1相鄰的點(diǎn)，即;②具有T標(biāo)號(hào)，即，為T(mén)標(biāo)號(hào)點(diǎn)集.修改的T標(biāo)號(hào)為，并將結(jié)果仍記為T(mén)(vj)。svj?若網(wǎng)絡(luò)圖中已無(wú)滿足此條件的T標(biāo)
3、號(hào)點(diǎn)，停止計(jì)算。第三步：令,然后將的T標(biāo)號(hào)改成P標(biāo)號(hào)，轉(zhuǎn)入第二步。此時(shí)，要注意將第二步中的改為。例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（2）例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421（4）v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：237184566134105275934682求從1到8的最短
4、路徑237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={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,2,4}min{d1
5、6,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,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,2,4,6,7}min
6、{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,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=82371845
7、66134105275934682X={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,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10
