dijikstra.m

10组图论编程

function y=dijikstra(G,start,term)
%G矩阵中0代表重点，inf代表无连接。
%start 表示始点，term为终点。
%此算法可用于无向图，也可用于有向图。
%图中的权必须非负，负权图的最短路算法需用佛ford算法
M=inf;
a(1,:)=[0,50,M,40,25,10]; 
a(2,:)=[zeros(1,2),15,20,M,25]; 
a(3,:)=[zeros(1,3),10,20,M]; 
a(4,:)=[zeros(1,4),10,25]; 
a(5,:)=[zeros(1,5),55]; 
a(6,:)=zeros(1,6); 
a=a+a'; 
if nargin==0
   start=1;
   term=4;
   G=a;
end;
N=length(G);
[i,j]=find((G~=0)&(G~=M));
d=G(find((G~=0)&(G~=M)));
data=[i';j'];
u=zeros(1,N); 
u(1,:)=inf;
u(start)=0;
v=u;
%采用标号法，u是各点的标号。
p=[1];
%p纪录已经标号的点。
index(1)=0;
%index(i)表示始点到i点的最短路上，i的前一个点。
n=0;
%n表示已标号的点的个数。
while n~=N
    [s,x]=min(v);
    v(:,x)=inf;
     n=n+1;
    [i,j]=find(data(1,:)==x);
    for e=1:length(i)
         temp=data(2,j(e));
%temp是与i相邻的且未标号的点。
         if u(temp)>(s+G(x,temp))
             u(temp)=(s+G(x,temp));
             v(temp)=u(temp);
             index(temp)=x;
             p=[p,temp];
         end
     end
 end
reslut=[];
temp1=index(term);
while temp1~=start
   reslut=[reslut,temp1];
   temp1=index(temp1);
end
reslut=[reslut,temp1];
y=reslut;
end