algorithm - MATLAB 中 MST 的总路径长度

Question

大家好。

我有一个大小为 (1200x1200) 的最小生成树 (MST) 的邻接矩阵，我希望找到矩阵形式的节点之间的总路径长度。

例如，如果我有一个大小为 (4x4) 的邻接矩阵，如下所示，
然后显示总路径长度矩阵。

节点 1 和节点 4 之间的总路径长度为 3，即从节点 1 到节点 4 的边数，反之亦然。

就我而言，我尝试使用 Dijkstra 算法来查找节点之间的总路径长度。如果我设置起始节点和目标节点，我需要做 (1200*1199)/2 次计算。于是，我尝试用loop函数来解决计算题。但是，这个过程已经运行了两天，仍然没有得到想要的结果......

请问:在大型MST中，有没有高效的求总路径长度的算法？

谢谢。

Answer 1

编辑:更新代码以说明同一 parent 的 child 之间的距离(应始终为 2)。

这似乎有效。我采用广度优先遍历而不是深度优先遍历，以限制堆栈上的节点数量。

从当前的父节点(我们从节点 1 开始)，我们找到 P 的子节点 C 到每个先前访问过的节点的距离。这只是从这些节点到 P 的距离，加上从 P 到 C 的距离，即 1。

然后我们将 child 添加到堆栈中，并通过将邻接矩阵中的行 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