大家好。
我有一个大小为（1200x1200）的最小生成树（mst）的邻接矩阵，我希望找到矩阵形式的节点之间的总路径长度。
例如，如果我有一个大小为（4x4）的邻接矩阵，如下所示，
然后给出了总路径长度矩阵。
节点1和节点4之间的总路径长度为3，即从节点1到节点4的边数，反之亦然。
在我的例子中，我尝试使用dijkstra的算法来计算节点之间的总路径长度。如果设置了起始节点和目标节点，则需要进行（1200*1199）/2次计算所以，我尝试使用循环函数来解决计算问题但是，这个过程已经运行了两天，仍然没有达到预期的效果…
我想问：有没有什么有效的算法来计算大mst中的总路径长度？
谢谢您。
最佳答案
编辑：更新代码，以说明同一父级的子级之间的距离（应始终为2）。
这似乎管用。为了限制堆栈上的节点数量，我使用了广度优先遍历而不是深度优先遍历。
从当前父节点（我们从节点1开始）我们可以找到从P的子节点C到之前访问的每个节点的距离这只是从这些节点到p的距离，加上从p到c或1的距离。
然后，我们将子级添加到堆栈中，并通过将邻接矩阵中的行P和列P设置为0将P标记为已访问。继续，直到所有节点都已访问（堆栈为空）。
A = [0 1 0 0; %// Adjacency matrix
1 0 1 0;
0 1 0 1;
0 0 1 0]
D = zeros(size(A)); %// Distance matrix
S = [1]; %// The stack initially contains Node 1
while numel(S) > 0
P = S(end); %// Pop the top element from the stack
S = S(1:end-1);
C = find(A(P,:)); %// Get all children of P
for child = 1:numel(C)
%// Distance to child = distance to parent + 1
%// for non-zero distances only
D(C(child),:) = D(P,:)+(D(P,:)>0);
%// Distance to child from parent is 1
D(C(child),P) = 1;
S(end+1) = C(child); %// Add child to stack
%// This doesn't seem like the most elegant solution
%// but it should work.
if child > 1 %// Update distance to previous siblings
for sib = 1:child-1
D(C(child),C(sib)) = 2;
end
end
end
A(P,:) = 0; %// Delete parent from adjacency matrix
A(:,P) = 0;
end
D = D + D.' %// We've only found D(s,t)... add D(t,s)
示例矩阵的输出为：
A =
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
D =
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0