hao
function =minRoute(i,m,W)%图与网络论中求最短路径的Dijkstra算法 M-函数
%格式 =minroute(i,m,W)
% i为最短路径的起始点,m为图顶点数,W为图的带权邻接矩阵，
% 不构成边的两顶点之间的权用inf表示。显示结果为：S的每
% 一列从上到下记录了从始点到终点的最短路径所经顶点的序号；
% D是一行向量，记录了S中所示路径的大小;
%例如
% clear;w=inf*ones(6);w(1,3)=10;w(1,5)=30;
% w(1,6)=100;w(2,3)=5;w(3,4)=50;w(4,6)=10;
% w(5,4)=20;w(5,6)=60;
% i=1;=minroute(i,6,w)
% By X.D. Ding June 2000
dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=;
% dd的第二行是每次求出的最短路径的终点，第一行是最短路径的值
kk=2;=size(dd);
while ~isempty(V)
=min(W(i,V));tmpj=V(j);
for k=2:ndd
=min(dd(1,k)+W(dd(2,k),V));
tmp2=V(jj);tt(k-1,:)=;
end
tmp=;=min(tmp(:,1));
if tmp3==tmpd, ss(1:2,kk)=;
else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);
if dd(2,tmp4)==ss(tmp6,tmp4)
ss(1:tmp6+1,kk)=;
else, ss(1:3,kk)=;
end;end
dd=];V(tmp(tmp4,3))=[];
=size(dd);kk=kk+1;
end; S=ss; D=dd(1,:);
{:3_41:}{:3_41:}{:3_41:} 。。。。。。。。。。。。。。。。。。。。。。。。。。
页:
[1]