MATLAB-Dijkstra演算法

04-27

第一次看到這個演算法是在司守奎的書上見到的，看了很久都沒有看懂，後來查了很多的資料，算是懂了一點點，書中對開頭部分

給出了數學表達式，大部分非CS的應該看的比較不舒服。

不啰嗦，直接上案例分析：(圖丑，見諒)

數模課堂習題

數模

step 1.

給 $v_{1}$ 以 P編號，給其他的點以 T編號

且 $P(v_{1})=0 , T(v_{i})=inf$

step 2.

對於 $T(v_{2})=min(T_v(2),P_{v_{1}}+l_{12})=3$

$T(v_{3})=min(T_v(3),P_{v_{1}}+l_{13})=5$

則 $min(T_{v_{i}})=min(T_{v_{2}},T_{v_{3}},T_{v_{4}},T_{v_{5}},T_{v_{6}})$

so ： $T_{v_{2}}=3 則 P_{v_{2}}=3$

（PS：若此處出現兩個最小值，任選一個y即可）;

step 3.

$T_{v_{3}}=min(T_{v_{3}},P_{v_{2}}+l_{23})=4$

$T_{v_{4}}=min(T_{v_{4}},P_{v_{2}}+l_{24})=5$

$T_{v_{5}}=min(T_{v_{5}},P_{v_{2}}+l_{25})=5$

$T_{v_{6}}=inf$

$min(T_{v_{i}})=min(T_{v_{3}},T_{v_{4}},T_{v_{5}},T_{v_{6}})$

$T_{v_{3}}=4 即 P_{v_{3}}=4$

step4.

$T_{v_{5}}=min(T_{v_{5}},P_{v_{3}}+l_{23})=5$

$min(T_{v_{j}})=min(T_{v_{4}},T_{v_{5}},T_{v_{6}})=T_{v{4}}=T_{v_{6}}=5$

$故: p_{v_{4}}=p_{v_{5}}=5$

step 5.

$T_{v_{6}}=min(T_{v_{6}},P_{v_{4}}+l_{46},P_{v_{5}}+l_{56})=7$ $則 P_{v_{6}}=7$

逆推可得最短路為 $V_{1} ightarrow V_{2} ightarrow V_{5} ightarrow V_{6}$

寫成MATLAB程序則為：

clc,clearn=6; a=zeros(n);a(1,2)=3; a(1,3)=5;a(2,4)=2; a(2,5)=2; a(2,3)=1;a(3,5)=4;a(4,5)=2; a(4,6)=4;a(5,6)=2;a=a+a;a(a==0)=inf; %為方便，將對角線上的元素和沒有連線的路用inf表達二者距離pb(1:n)=0; pb(1)=1; %當一個點已經求出到原點的最短距離時，其下標i對應的pb(i)賦1index1=1 ; %存放存入S集合的順序index2=ones(1,n); %存放始點到第i點最短通路中第i頂點前一頂點的序號d(1:n)=inf; %存放由始點到第i點最短通路的值d(1)=0; %本次起始點是1，故d=0temp=1; %表示起始點while sum(pb)<n %是否所有的點都被標記了 tb=find(pb==0); %找到為0的值，表示未在集合S中 d(tb)=min(d(tb),d(temp)+a(temp,tb));%計算標號為0的最短路，計算公式在開頭圖中給出 tmpb=find(d(tb)==min(d(tb)));%找到d[tb]最小值的下標 temp=tb(tmpb(1));%可能存在多個最小值，只取一個，並且此時的原點也會變為下一個原點 pb(temp)=1;% 找到最小路，打上標記 index1=[index1,temp]%將打上標記的存入S集合中 temp2=find(d(index1)==d(temp)-a(temp,index1));%最小路徑 index2(temp)=index1(temp2(1));%記錄標號索引①endd,index1,index2

①：根據循環可得：

$d(1)=d(2)-a(2,1)$

$d(2)=d(3)-a(3,2)$

$d(2)=d(4)-a(4,2)$

$d(2)=d(5)-a(5,2)$

$d(5)=d(6)-a(6,5)$

湊合看看

因此因此我們可以得到最短路程所對應的最短路徑

附上個人代碼（複製粘貼到上方代碼後方即可）

i=zeros(1,n); i(1)=n; %逆推法，從最後一項開始for j=2:n i(j)=index2(i(j-1)); if i(j)==1 break endendi=i(i~=0); %去除非0元素for ii=length(i):-1:1 %倒著輸出 if ii~=length(i) fprintf(-->) end fprintf(v(%d),i(ii))endfprintf( )

運行結果

其他優秀的Dijkstra博文：

1.對於書中的例子由很詳細的講解

迪克斯特拉（Dijkstra）演算法之MATLAB實現 - CSDN博客?

blog.csdn.net
推薦閱讀：

※思維導圖入門應該知道的一些小知識
※「教練，我想打籃……額不，做皮具，怎麼入門？」

TAG:MATLAB | 入門指南 |