1

我正在实施Floyd-Warshall 算法。

我有大约 50 个节点的完整图，我想找到所有节点之间的最大路径。算法返回的路径可以是任何长度 1< x<50，我需要这个长度最多为 3-4 条边长，我该如何更改算法呢？

4

1 回答 1

1

令w(i,j)为从i到j的权重。然后你可以计算

def shortest(w1, w2):
  w12 = a new V x V matrix
  for i in V:
    for j in V:
      w12(i, j) = w1(i, j)
      for k in V:
        if w12(i, j) > w1(i, k) + w2(k, j):
          w12(i, j) = w1(i, k) + w2(k, j)
  return w12

w2 = shortest(w, w)
w3 = shortest(w2, w)
w4 = shortest(w2, w2)

最后，w4将包含每对从开始到结束的距离，最多使用 4 条边，对于w3. 请注意，您可以w4在不w3先计算的情况下进行计算。使用这种形式的二值化，即计算和组合所有的二次方矩阵，您可以实现 O(n³ log k) 的时间复杂度，即最大路径长度仅为对数。

维基百科有一篇关于上述算法的短文。它的标题是“<a href="https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication" rel="nofollow">min-plus 矩阵乘法”。也许与该术语或替代术语“距离乘积”相关的一些参考资料将导致有关可能实现的更多信息。例如，有一篇论文《<a href="http://www.research.ibm.com/trl/people/yanagis/papers/RT0932.pdf" rel="nofollow">faster funny matrix multiplication for the all -pairs shortest paths problem”，其中讨论了这个问题，给出了一些算法，并考虑了 SIMD 的实现。

于 2013-05-07T00:02:41.097 回答