restrict Floyd-Warshall to a path length k

Question

I'm implementing Floyd-Warshall algorithm.

I have the full-graph with around 50 nodes, I want to find the maximum path between all nodes. the paths that the algorithm returns can be in any length 1< x<50, I need this length to be at most 3-4 edges long, how can I change the algorithm to do so?

Answer 1

Let w(i,j) be the weight from i to j. Then you can compute

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)

At the end, w4 will contain for each pair the distance from start to end using up to 4 edges, and similarly for w3. Note that you can compute w4 without computing w3 first. Using this form of binarization, i.e. computing and combining all power-of-two matrices, you can achieve a time complexity of O(n³ log k), i.e. only logarithmical in the maximal path length.

Wikipedia has a short article on the algorithm outlined above. It is titled “min-plus matrix multiplication”. Perhaps some references associated with this term, or the alternate term “distance product”, will lead to further information on possible implementations. For example, there is a paper “faster funny matrix multiplication for the all-pairs shortest paths problem” which discusses this problem, gives some algorithm, and thinks about SIMD implementations.