shuzhifenxi.zip_matlab数值算法_数值分析MATLAB_数值分析算法_数值算法

%%最短路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