0
\$\begingroup\$

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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        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];
            List<Integer> currentGraph = new LinkedList<>();
            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
                            }
                        }
                    }
                }
                // add to graph
                currentGraph.add(nv);
                // 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]);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

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

        public String nextLine() {
            try {
                return reader.readLine();
            } 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:

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.