function Dijkstra(w,start,MAX)

%w为此图的距离矩阵

%start为起始端点下标（从1开始）

%MAX是数据输入时的∞的实际值

%2011年6月19日17:02:03

len=length(w);

flag=zeros(len,2);

index=zeros(1,len);

index(1)=start;

%根据路由类型初始化路由表

R=ones(len,2)*MAX;

R(1,1)=0;

R(1,2)=start;

port=zeros(1,len);

port(start)=0;

%处理端点有权的问题

for i=1:len

tmp=w(i,i)/2;

if tmp~=0

w(i,:)=w(i,:)+tmp;

w(:,i)=w(:,i)+tmp;

flag(i,1)=1; %表示端i点有权值

flag(i,2)=tmp; %存储端点权值的一半

end

w(i,i)=MAX;

end

s=sprintf('\\tv%d',1:len);

s_tmp=sprintf('\\t|%s\\t%s\\t',' 置定端',' 距离');

s=strcat(s,s_tmp);

s_tmp=sprintf('%s\\t',' 路由 ');

s=strcat(s,s_tmp);

s_tmp=sprintf('\----------------------------------------------------\\\t0');

s=strcat(s,s_tmp);

for i=1:len-1

s_tmp=sprintf('\\t∞');

s=strcat(s,s_tmp);

end

s_tmp=sprintf('\\t|\\t%d\\t%4.1f\\t%d',start,0,start);

s=strcat(s,s_tmp);

disp(s);

%Dijkstra算法具体实现过程

count=1;

while count<len

s='';

N=MAX; %暂存每次距离比较的较大值

x=1; %暂存每次距离比较的较大值的下标

for i=1:len

if isempty(find(index==i,1)) %将没有在置定点的i值跳过

continue

end

for j=1:len

if ~isempty(find(index==j,1)) %将在置定点的j值跳过

continue

else

port(j)=R(i,1)+w(i,j); %新距离

end

if port(j)<R(j,1) %新旧路由距离比较，如果小，则更新

R(j,1)=port(j);

R(j,2)=i;

else

port(j)=R(j,1);

end

if port(j)<N %通过比较，得出一次循环中，最小的距离，将相应点置定

N=port(j);

x=j;

end

end

end

for k=1:len %输出格式设置(考虑端权值)

if isempty(find(index==k,1))

if port(k)==MAX

s_tmp=sprintf('\\t%s','∞');

else

if flag(k,1)

port(k)=port(k)-flag(k,2);

end

s_tmp=sprintf('\\t%2.1f',port(k));

end

else

s_tmp=sprintf('\\t%s','_');

end

s=strcat(s,s_tmp);

end

if flag(x,1)

R(x,1)=R(x,1)-flag(x,2);

end

s_tmp=sprintf('\\t|\\t%d\\t%4.1f\\t%d',x,R(x,1),R(x,2));

s=strcat(s,s_tmp);

disp(s);

%为下次的循环设置条件——更新置定点列表+count加1

count=count+1;

index(count)=x;

end

end

示例：

输入：

b=[

0,9.2,1.1,3.5,100,100;

1.3,0,4.7,100,7.2,100;

2.5,100,0,100,1.8,100;

100,100,5.3,0,2.4,7.5;

100,6.4,2.2,8.9,0,5.1;

7.7,100,2.7,100,2.1,0

];

Dijkstra(b,1,100