%%最短路Dijkstra算法
function [d,path]=shortpath(A,s,t)
%A为赋权邻接矩阵
%s为起点（源点），t为终点
%当输入参数为2个时，计算s到各顶点的最短路径
%为3个时，计算s到t的最短路径
if nargin==2
flag=0;
elseif nargin==3
flag=1;
end
n=length(A);%当行与列数不等时，返回其最大值
for i=1:n
A(i,i)=inf;%将邻接矩阵的对角线赋值inf，即i-i路径关闭
end
V=zeros(1,n);%装顶点小标，即路径
D=zeros(1,n);%装距离
T=A+inf;%用来装s到各顶点的路径距离（权值）
T(s,:)=A(s,:);%将邻接矩阵s行赋给T矩阵s行
A(s,:)=inf;
for j=1:n-1%当j=1时找s到各顶点的最短路径
[p,q]=min(T)
q1=q;
[p,q]=min(p);
V(q)=q1(q);
if flag==1&q==t
d=p;
break;
else
D(q)=p;
A(:,q)=inf;
T(q,:)=A(q,:)+p;%找到每一次的顶点后，修改从这个顶点出去的边的权值（前面计算好最短的+出去的边）
T(:,q)=inf;%顶点已完成，将进入这个顶点的边关闭（禁止）
T(:,s)=inf;%关闭这个顶点返回到源点路径
end
end
if flag==1
path=t;
while path(1)~=s
path=[V(t),path];
t=V(t);
end
else
for i=1:n
if i~=s
path0=i;
v0=i;
while path0(1)~=s
path0=[V(i),path0];
i=V(i);
end
d=D;
path(v0)={path0};
disp([int2str(s),'->',int2str(v0),'d=',int2str(D(v0)),'path=',int2str(path0)]);
end
end
end
