最短路徑問(wèn)題的算法分析及建模案例-文庫(kù)吧資料
2025-04-23 02:11本頁(yè)面
【正文】 s(1)。ends=[]。 %賦初值%for i=1:nl(i)=w1(i)。inf inf inf inf 9 6 3 0]n=size(w,1)。inf inf inf 1 3 0 4 6。8 6 7 0 5 1 2 inf。2 0 inf 6 1 inf inf inf 。迭代次數(shù) 1020218328104831058610126710127912812最后標(biāo)記L（v）021736912Z（v）因此得到最短路徑為：迭代次數(shù) 最后標(biāo)記L（v）021736912Z（v）由上表可得到到各點(diǎn)的最短路徑為：；；，；；；，；。現(xiàn)要從區(qū)向其他各區(qū)運(yùn)水，求出區(qū)到其他各區(qū)的最短路徑。（4） 按照上述步驟繼續(xù)計(jì)算。得到一條從到v的最優(yōu)路徑。將s標(biāo)號(hào)為/，表示節(jié)點(diǎn)到s的最優(yōu)路徑的長(zhǎng)度且與s相鄰。（2） 按照每個(gè)沒(méi)有標(biāo)號(hào)的節(jié)點(diǎn)w計(jì)算，表示節(jié)點(diǎn)t到節(jié)點(diǎn)w之間的權(quán)值。 Dijkstra算法的計(jì)算步驟最短路徑問(wèn)題是指在一個(gè)賦予權(quán)值的圖的兩個(gè)指定節(jié)點(diǎn)和v之間找出一條具有最小權(quán)值的路。 Dijkstra算法的理論依據(jù)（1） 對(duì)于S中任意一頂點(diǎn)，其永久標(biāo)號(hào)都是從頂點(diǎn)到該頂點(diǎn)的最短路的長(zhǎng)度。一般的，算法在被臨時(shí)標(biāo)號(hào)的頂點(diǎn)中尋找一個(gè)頂點(diǎn)，其臨時(shí)標(biāo)號(hào)最小，然后將賦予永久標(biāo)號(hào)，并且對(duì)其余臨時(shí)標(biāo)號(hào)的頂點(diǎn)vj按照方式修正其標(biāo)號(hào)。三 最短路徑算法研究 Dijkstra算法 Dijkstra算法的基本思想對(duì)網(wǎng)絡(luò)中每個(gè)頂點(diǎn)賦一個(gè)標(biāo)號(hào)，用來(lái)記錄從頂點(diǎn)到該頂點(diǎn)的最短路的長(zhǎng)度（稱為永久標(biāo)號(hào)）或最短長(zhǎng)度的上界（稱為臨時(shí)標(biāo)號(hào)）。設(shè)G=（V,A,w）是一個(gè)有向網(wǎng)絡(luò)，p為G中一條有向路，稱w（P）=為路徑p的路長(zhǎng)。如何選擇航線以達(dá)到要求。二 最短路問(wèn)題定義：所謂最短路徑是指如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一跳有向路徑使得沿這條路徑上各弧的權(quán)值總和最小。類似的可定義有向跡，有向路，有向閉途徑，有向閉跡，有向回路（圈）等。如果圖G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖。顯然路必為跡，但反之不一定成立。 完全有向圖定義：設(shè)G=（V,E）是一個(gè)簡(jiǎn)單有向圖，則|A|不大于
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1