将Floyd-Warshall限制为路径长度k

Question

我正在实现Floyd-Warshall algorithm。

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

Answer 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也是如此。请注意，您可以在不先计算w3的情况下计算w4。使用这种形式的二值化，即计算和组合所有2的幂矩阵，您可以实现O(n³log )的时间复杂度，即最大路径长度仅为对数。

维基百科上有一篇关于上述算法的短文。它的标题是“min-plus matrix multiplication”。也许与这个术语相关的一些参考文献，或者替代术语“距离乘积”，将导致关于可能的实现的进一步信息。例如，有一篇名为“faster funny matrix multiplication for the all-pairs shortest paths problem”的论文讨论了这个问题，给出了一些算法，并考虑了单指令多路复用的实现。