clear all
%圖論最短路問題的Dijkstra算法
%鄰接矩陣(點與點的關(guān)系)
w=[0,2,4,inf,inf,inf,inf;  
   2,0,inf,3,3,1,inf;
   4,inf,0,2,3,1,inf;                      
   inf,3,2,0,inf,inf,1;                    
   inf,3,3,inf,0,inf,3;
   inf,1,1,inf,inf,0,4;
   inf,inf,inf,1,3,4,0];
n=size(w,1);%記錄圖中點數(shù)
for i=1:n
l(i)=w(1,i);%為l(v)賦初值
z(i)=1;     %為z(v)賦初值1
end
s=[];       %s集合
s(1)=1;     %s集合的第1個元素為起點
u=s(1);
k=1;        %k記錄集合s中點的數(shù)量

while k<n   %當(dāng)集合s未包含所有元素的時候執(zhí)行循環(huán)
 for i=1:n  %更新一遍l(v),z(v)
 if l(i)>l(u)+w(u,i)
 l(i)=l(u);
 z(i)=u;
 end
 end
%找l(i)中最小的v加入s集合
 ll=l;
 for i=1:n
 for j=1:k
     if i==s(j)
     ll(i)=inf;%去除掉已經(jīng)在s集合中的點
     end 
 end
 end
[lv,v]=min(ll);%求最小的l(v)
s(k+1)=v;      %加入集合s
u=v;
k=k+1;
end

fprintf('最短路為:%1d->%1d->%1d->%1d\n',z(z(z(7))),z(z(7)),z(7),7)