Matlab dijkstra算法
function [distance,path]=dijkstra(A,s,e)
% [DISTANCE,PATH]=DIJKSTRA(A,S,E)
% returns the distance and path between the start node and the end node. % A: adjcent matrix
% s: start node
% e: end node
% initialize
n=size(A,1); % node number
D=A(s,:); % distance vector
path=[]; % path vector
visit=ones(1,n); % node visibility
visit(s)=0; % source node is unvisible
parent=zeros(1,n); % parent node
distance=D(e);
% the shortest distance path
if parent(e)==0, return; end
path=zeros(1,2*n); % path preallocation
t=e; path(1)=t; count=1;
while t~=s && t>0
p=parent(t);
path=[p path(1:count)];
t=p; count=count+1;
end
if count>=2*n, error(['The path preallocation length is too short.',...
'Please redefine path preallocation parameter.']);
end
path(1)=s;
path=path(1:count);
function [y,fval,flag]=Hungary(C)
%********************************************************************** % >> C=[2 15 13 4;10 4 14 15;9 14 16 13;7 8 11 9]
% >> [y,fval]=Hungary(C)
% M =
% 0 0 0 1
% 0 1 0 0
% 1 0 0 0
% 0 0 1 0
% y =
% 28
% >>
%********************************************************************** *****
[m,n]=size(C);
tempC=C;
for i=1:m
tempC(i,:)=tempC(i,:)-min(tempC(i,:));
end
for i=1:n
tempC(:,i)=tempC(:,i)-min(tempC(:,i));
end
tempC=TryAssign(tempC);
OneNumber=0;
while OneNumber<m
Row=zeros(m,1);
Col=ones(1,n);
Line=[];
for i=1:m
if IsInMatrix(inf,tempC(i,:))==0
Line=[Line,i];
Row(i)=1;
end
end
for i=Line
Cur=i;
while Cur~=0
[Cur,Row,Col]=ZeroCover(tempC,Row,Col,Cur); end
end
temp=inf;
for i=1:m
for j=1:n
if tempC(i,j)==inf|tempC(i,j)==-inf
tempC(i,j)=0;
end
end
end
for i=1:m
if Row(i)==1
tempC(i,:)=tempC(i,:)-temp;
end
end
for j=1:n
if Col(j)==0
tempC(:,j)=tempC(:,j)+temp;
end
end
tempC=TryAssign(tempC);
OneNumber=0;
end
AssignMatrix=zeros(m,n);
for i=1:m
for j=1:n
if tempC(i,j)==inf
AssignMatrix(i,j)=1;
end
end
end
y=AssignMatrix;
temp=C.*AssignMatrix;
fval=sum(temp(:));
function y=IsInMatrix(a,A);
[m,n]=size(A);
y=0;
for i=1:m
for j=1:n
if A(i,j)==a
y=1;
break;
end
end
if j<n
break;
end
end
function y=TryAssign(C)
[m,n]=size(C);
while IsInMatrix(0,C)==1
flag=0;
for i=1:m
if ZeroNumber(C(i,:))==1
temp=C(i,:);
ZeroRowPos=find(temp==0);
C(i,ZeroRowPos)=inf;
temp=C(:,ZeroRowPos);
ZeroColPos=find(temp==0);
for j=ZeroColPos
C(j,ZeroRowPos)=-inf;
end
flag=flag+1;
end
end
for i=1:n
if ZeroNumber(C(:,i))==1
temp=C(:,i);
ZeroColPos=find(temp==0);
C(ZeroColPos,i)=inf;
temp=C(ZeroColPos,:);
ZeroRowPos=find(temp==0);
for j=ZeroRowPos
C(ZeroColPos,j)=-inf;
end
flag=flag+1;
end
end
if flag==0
temp=inf;
for i=1:m
if (ZeroNumber(C(i,:))<temp) & (ZeroNumber(C(i,:))>0) temp=ZeroNumber(C(i,:));
ZeroRow=i;
end
end
temp1=find(C(ZeroRow,:)==0);
temp2=inf;
for i=temp1
if (ZeroNumber(C(:,i))<temp2) & (ZeroNumber(C(:,i))>0)
temp2=ZeroNumber(C(:,i));
ZeroCol=i;
end
end
C(ZeroRow,ZeroCol)=inf;
temp=find(C(ZeroRow,:)==0);
for i=temp
C(ZeroRow,i)=-inf;
end
temp=find(C(:,ZeroCol)==0);
for i=temp
C(i,ZeroCol)=-inf;
end
end
end
y=C;
function [y,Row,Col]=ZeroCover(C,Row,Col,Cur) [m,n]=size(C);
temp=C(Cur,:);
flag=0;
Cur=[];
for i=1:m
if temp(i)==-inf & Col(i)~=0
Col(i)=0;
Cur=[Cur,i];
flag=1;
end
end
if flag==0
y=0;
else
for i=Cur
temp=C(:,i);
for i=1:m
if temp(i)==inf & Row(i)==0
Row(i)=1;
y=i;
flag=0;
[y,Row,Col]=ZeroCover(C,Row,Col,y);
break;
end
end
if flag==1
y=0;
end
end
end
function y=ZeroNumber(A)
y=0;
for i=1:length(A)
if A(i)==0
y=y+1;
end
end。