Question

图论中求解最短路的dijkstra法的MATLAB程序中最后的矩阵DD是什么意思？请高手指点！

MATLAB程序：
function [d,DD]=dijkstra(D,s)
%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路
%D为赋权邻接矩阵
%d为s(图中顶点)到其它各点最短路径的长度
%DD记载了最短路径生成树
[m,n]=size(D);
d=inf.*ones(1,m);
d(1,s)=0;
dd=zeros(1,m);
dd(1,s)=1;
y=s;
DD=zeros(m,m);
DD(y,y)=1;
counter=1;
while length(find(dd==1))<m
for i=1:m
if dd(i)==0
d(i)=min(d(i),d(y)+D(y,i));
end
end
ddd=inf;
for i=1:m
if dd(i)==0&&d(i)<ddd
ddd=d(i);
end
end
yy=find(d==ddd);
counter=counter+1;
DD(y,yy(1,1))=counter;
DD(yy(1,1),y)=counter;
y=yy(1,1);
dd(1,y)=1;
end
输出结果：
>> [d,DD]=dijkstra(W,1)

d =

0 5 3 1 6 10 9 11 8

DD =

1 0 0 2 0 0 0 0 0
0 0 4 0 5 0 0 0 0
0 4 0 3 0 0 0 0 0
2 0 3 0 0 0 0 0 0
0 5 0 0 0 0 0 0 6
0 0 0 0 0 0 8 9 0
0 0 0 0 0 8 0 0 7
0 0 0 0 0 9 0 0 0
0 0 0 0 6 0 7 0 0
DD中的数字表达什么意思，或者DD表达什么意思，我不懂。。。。

提示该问答中所提及的号码未经验证，请注意甄别。

Answer 1

你的源代码中不说明了，DD表示最短路径的生成树嘛！
你看DD矩阵中的数字，是一个对称矩阵，根据该矩阵就可以知道，最短路径的通路是:
1->4->3->2->5->9->7->6->8(数字表示结点的号码)，这条路径的权重(你可以理解为距离)就是11，由D给出。
实际上由D你也可以推出这条路径，只不过，D是用一维表示方法(根据权重)，而DD是二维表示方法(根据下一个结点，所以就是1、2、3....)。
--------------------------------
你对照DD画出一张图，你就明白了。
有数字的就画线，并标明权重，是0就不画线。

Answer 2

DD是最短路径生成树
具体的可以看看数据结构那本书中的说明，不知道图论书里面有没有，我是在数据结构里面学的

Answer 3

楼上的程序怎么调不出来，显示有错误，初学者跪求答案。。。

追问

都两年了，早就不玩了。。。