# Incremental Floyd Warshall on directed graph

Given a directed graph with $$\n\le 500\$$ vertices I want to find sum of minimum distances between each pair. This can be done using Floyd-Warshall in $$\O(n^3)\$$. Now I remove a vertex and do so again until graph becomes empty. In this manner it would take $$\O(n^4)\$$ if I perform Floyd Warshall everytime.

My solution is to start backwards and perform FW on singleton graph then add a vertex to graph. and perform only the caluclations involving new vertex because rest of the graph is already minimized. Suppose we have $$\V=(a,b)\$$ and new vertex is $$\c\$$ then the shortest paths that can change and candidates are:

• a to b through c (and reverse) [old]
• a to c through b (and reverse) [new-old]
• b to c through a (and reverse) [new-old]

So I update respective distances. I have a gut feeling that repeating this operation twice will take care of any other update involving another vertex, suppose $$\V=(a,b,d)\$$ then say $$\a-b-c-d\$$ needs update. I feel like paths involving more than three of $$\V\$$ are already minimum, though I can't prove it. This would thus take $$\O(n^2)\$$ for introducing a new vertex and for all operations $$\O(n^3)\$$ However my code is not that time efficient.

The input consists of (i) number of vertices, (ii) adjacency matrix, (iii) order of vertices to remove.

I will output the sum of minimum distances between each pair before removal.

Here is my code submission which is exceeding time limit.

Legend: a is adjacency matrix, n is number of vertices, x is array containing vertices values in 1-indexed form to be removed in array order, fw is floyd-warshall matrix, relax(a, b, c) updates minimum distance from a to b (and reverse) considering alternative through c.

import java.io.*;
import java.util.*;

public class P295B {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(in, out);
out.close();
}

public void solve(InputReader in, PrintWriter out) {
int n = in.nextInt();
int[][] a = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = in.nextInt();
}
}
int[] x = in.nextIntArray(n);
int[][] fw = new int[n][n];
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i--) {
// add vertex x[i] to graph
int nv = x[i] - 1; // new vertex
for (int j : currentGraph) {
fw[nv][j] = a[nv][j];
fw[j][nv] = a[j][nv];
}
// compute shortest paths
for (int j = 0; j < 2; j++) {
for (int k : currentGraph) {
for (int l : currentGraph) {
if (l != k) {
// new and old
relax(fw, nv, k, l); // nv -> l -> k and reverse
relax(fw, nv, l, k); // nv -> k -> l and reverse
// old
relax(fw, k, l, nv); // k -> nv -> l and reverse
}
}
}
}
// calculate sum of lengths of shortest paths
for (int j : currentGraph) {
for (int k : currentGraph) {
if (j != k) { ans[i] += fw[j][k]; }
}
}
}
for (int aa : ans) {
out.print(aa + " ");
}
out.println();
}

private void relax(int[][] fw, int a, int b, int c) {
fw[a][b] = Math.min(fw[a][b], fw[a][c] + fw[c][b]);
fw[b][a] = Math.min(fw[b][a], fw[b][c] + fw[c][a]);
}
}

public StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

public String nextLine() {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}

public int[] nextIntArray(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) { arr[i] = nextInt(); }
return arr;
}

public long[] nextLongArray(int n) {
long[] arr = new long[n];
for (int i = 0; i < n; i++) { arr[i] = nextLong(); }
return arr;
}

}

}


Question:

• What, if any, is there a problem in the implementation that is leading to a degradation of time performance from expected $$\O(n^3)\$$. For a rough estimate, in worst case, total operations are of order $$\500*501*1001/6=4.1\times10^7\$$. Given $$\3\$$ seconds on a $$\2.5{\rm Ghz}\$$ machine we have space for $7.5\times10^9$ providing space for a constant of $182$ elementary operations. I believe it to be enough for my implementation. Can you suggest improvements/point out mistakes?

Notes: