matlab最短路徑算法(編輯修改稿)
2025-06-15 18:40 本頁面
【文章內(nèi)容簡介】 1。 while path(i)~=start path(i+1)=f(path(i))。 i=i+1 。 end path(i)=start。 L=length(path)。 path=path(L:1:1)。 ① ② ③ 9 最短路徑算法 Dijkstra算法程序的使用說明： 調(diào)用格式為 [min,path]=dijkstra(w,start,terminal), 其中輸入變量 w為所求圖的帶權(quán)鄰接矩陣， start, terminal分別為路徑的起點(diǎn)和終點(diǎn)的號(hào)碼。返回 start到 terminal的最短路徑 path及其長度 min. 注意：頂點(diǎn)的編號(hào)從 1開始連續(xù)編號(hào)。 最短路徑算法 Floyd算法 使用范圍 : 1) 求每對(duì)頂點(diǎn)的最短路徑 。 2) 有向圖、無向圖和混合圖 。 算法思想 : 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出 n個(gè)矩陣 D(1), D(2), …, D(n), D(n) 是圖的距離矩陣 , 同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑 . 10 2 3 7 4 11 6 5 9 8 1 3 5 12 2 10 6 1 5 8 8 7 9 9 3 2 2 7 Floyd算法 —— 算法步驟 d(i,j) : i到 j的距離 。 path(i,j): i到 j的路徑上 i的后繼點(diǎn) 。 輸入帶權(quán)鄰接矩陣 a(i,j). 1）賦初值 對(duì)所有 i,j, d(i,j)?a(i,j) , path(i,j)?j,k=l. 2）更新 d(i,j) , path(i,j) 對(duì)所有 i,j, 若 d(i,k)+d(k,j)d(i,j),則 d(i,j)?d(i,k)+d(k,j) , path(i,j)?path(i,k) , k ?k+1 3）重復(fù) 2)直到 k=n+1 MATLAB程序（ Floyd算法） function [D,path,min1,path1]=floyd(a,start,terminal) D=a。n=size(D,1)。path=zeros(n,n)。 for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j。 end, end, end for k=1:n for i=1:n for j=1:n
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1