Question

以下是我在网上下的关于用Dijkstra算法算最短路的Matlab程序，望各位大神解释解释里面循环的含义

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,:);

要是能改为vb.net或C#的代码就更好了，求指导！！

Answer 1

lz给个邮箱，我发给你些资料，首先你先得弄明白D算法是什么样的否则怎么看也看不懂的。我有一段代码，可以解释给你听。

function [leng,path] = dijkstra(adj_mat , sta , dst)
m = length(adj_mat);
lengs = linspace(0,0,m);
paths = linspace(0,0,m);
know = linspace(0,0,m);
know(1) = sta;
k=1;
for i = 1:1:m
if i ~= sta
lengs(i) = adj_mat(sta,i);
if lengs(i) ~= inf
paths(i) = sta;
end
end
end
index = 1;
for i = 1:1:m
if i ~= sta
min = inf;
for j = 1:1:m
count = isIn(know,j);
if count == 0 && lengs(j) <= min
k = j;
min = lengs(j);
end
end
know(index) = k;
index = index+1;
for j = 1:1:m
count = isIn(know,j);
if count == 0 && (lengs(i) + adj_mat(i,j)) < lengs(j)
lengs(j) = lengs(i) + adj_mat(i,j);
paths(j) = i;
end
end
end
end
leng = lengs(dst);
k = dst;
j = 1;
path = dst;
while paths(k)~= sta
k = paths(k);
path = [k path];
end
path = [sta path];

其实最关键的步骤就是if count == 0 && (lengs(i) + adj_mat(i,j)) < lengs(j)。判断两点距离与两点中间经过一点距离的大小，而过经过其他一点距离更小则替代原来的值！

至于c，matlab可以直接生成也可以上网找一个，很多的！

追问

非常感谢您的解答
787824563@qq.com