How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

Question

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time.

But in this case, we can't track actual shortest path with knowledge only two $d$ tables. It requires whole table.

There is a nice solution: Johnson's algorithm reduce both time and space complexity. (Especailly space complexity is $O(V^2)$) .

But I want to know can we apply simliar trick to Floyd-Warshall algorithm as Divide and Conquer trick in Sequence Alignment problem.

The crux part of Divide and Conquer trick in Sequence Alignment is 'we can reverse recursive relation into center'.

But in recursive relation in Floyd-Warshall algorithm, its recursive relation seems to be it has no such property.

Is there any other technique to apply such reducing space complexity that can track actual shortest path?

Edit: Also I want to retain time complexity $O(V^{(3+\epsilon)})$.

Answer 1

For each $i,j$ keep track of the last $k$ for which the value $d_{ij}^{(k)}$ was changed. That must be the highest value on the shortest path from $i$ to $j$. The actual path can be retrieved recursively.

Added. A simpler solution. Keep track of array $n_{ij}$ of vertices, giving the next vertex on the shortest path from $i$ to $j$. Whenever $d_{ij}^{(k)}$ changes, $n_{ij}$ is set to $n_{ik}$.

Answer 2

Function FloydWarshall(G = (V, E))
  set d[s][t] := infty for all s, t in V
  set parent[s][t] := null for all s, t in V
  foreach vertex u in V do
    d[u][u] := 0
  foreach edge e = (u, v) in E do
    d[u][v] := c(e)
    parent[u][v] := u
  for k := 1 to n do
    foreach vertex s in V do
      foreach vertex t in V do
        if d[s][k] + d[k][t] < d[s][t] then
          d[s][t] := d[s][k] + d[k][t]
          parent[s][t] := parent[k][t]
  return (d, parent)

Time complexity: $O\left(n^3\right)$
Space complexity: $O\left(n^2\right)$