function [S,D]=minRoute(i,m,W)
%圖與網絡論中求最短路徑的Dijkstra算法 M-函數
%格式 [S,D]=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;[s,d]=minroute(i,6,w)

% By X.D. Ding June 2000

dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];
% dd的第二行是每次求出的最短路徑的終點，第一行是最短路徑的值
kk=2;[mdd,ndd]=size(dd);
while ~isempty(V)
   [tmpd,j]=min(W(i,V));tmpj=V(j);
   for k=2:ndd
      [tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));
      tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];
   end
   tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));
   if tmp3==tmpd, ss(1:2,kk)=[i;tmp(tmp4,2)];
   else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);
      if dd(2,tmp4)==ss(tmp6,tmp4)
         ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];
         else, ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];
   end;end
   dd=[dd,[tmp3;tmp(tmp4,2)]];V(tmp(tmp4,3))=[];
   [mdd,ndd]=size(dd);kk=kk+1;
end; S=ss; D=dd(1,:);