資源描述：
《數(shù)學(xué)建模迪杰斯特拉算法例題.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、數(shù)學(xué)建模專題練習(xí)迪杰斯特拉算法2014.09例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先給v1以P標(biāo)號，給其余所有點(diǎn)T標(biāo)號。（2）v1v2v3v4v6v5352242421（4）v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：237184566134105275934682例二.求從1到8的最短路徑237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,
2、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{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,2,
3、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{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,d
4、53,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,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,
5、6,7,8}1到8的最短路徑為{1，4，7，5，8}，長度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10例三.下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費(fèi)用。現(xiàn)在某人要從v1出發(fā)，通過這個(gè)交通網(wǎng)到v8去，求使總費(fèi)用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363從v1到v8：P1=（v1，v2，v5，v8）費(fèi)用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）費(fèi)用3+2+10+2+4=21P3=……從v1到v8的旅行路線從v1到v8的路。旅行路線總費(fèi)用路上所有弧權(quán)之和。最
6、短路問題中，不考慮有向環(huán)、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路問題給定有向網(wǎng)絡(luò)D=（V，A，W），任意弧aij∈A，有權(quán)w（aij）=wij，給定D中的兩個(gè)頂點(diǎn)vs，vt。設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)（長度）是P中所有弧的權(quán)之和，記為w（P）。最短路問題就是要在所有從vs到vt的路中，求一條路P0，使稱P0是從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的路長。記為ust。當(dāng)所有wij≥0時(shí)，本算法是用來求給定點(diǎn)vs到任一個(gè)點(diǎn)vj最短路的公認(rèn)的最好方法。事實(shí)：如果P是D中從vs到vj的最短路
7、，vi是P中的一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。最短路的子路也是最短路。思想：將D=（V，A，W）中vs到所有其它頂點(diǎn)的最短路按其路長從小到大排列為：u0≤u1≤u2≤…≤unu0表示vs到自身的長度，相應(yīng)最短路記為：P0，P1，P2，…，Pn，取最小值的點(diǎn)為v1，∴P1=P（vs，v1）假定u0，u1，…，uk的值已求出，對應(yīng)的最短路分別為P1=P（vs，v1），P2=P（vs，v2），…，Pk=P（vs，vk）P1一定只有一條弧。記則使上式達(dá)到最小值的點(diǎn)v’可取為vk+1。計(jì)算過程中可采用標(biāo)號方法。Xk中的點(diǎn)，ui值是vs到vi的
8、最短路長度，相應(yīng)的點(diǎn)記“永久”標(biāo)號；XK中的點(diǎn)，ui
