1
$\begingroup$

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)})$.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Wrong. For each $i,j$, if you keep tracking while computing $d$, then you will use $O(V^3)$ in worst case. $i,j$ for $O(V^2)$ and length of path can be $O(V)$. $\endgroup$ – Maddy Dec 1 '15 at 1:18
  • $\begingroup$ Read carefully. Store a single $k$ for each $i,j$, not the path. $\endgroup$ – Hendrik Jan Dec 1 '15 at 3:01
  • $\begingroup$ Then your algorithm should not run in time not $O(V^3)$ in worst case because you can do $O(V)$ recursions, it can be $O(V^4)$. $\endgroup$ – Maddy Dec 1 '15 at 3:48
0
$\begingroup$
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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.