APSP

Question 1

How to solve APSP problem using SSSP solution for unweighted graph? + Time Complexity

Answer 1

Running BFS from each vertex. O(V^3) if E = O(V^2)

Question 2

How to solve APSP problem using SSSP solution for weighted graph? + Time Complexity (2 ways)

Answer 2

Running Bellman Ford V times, once from each vertex
- O(V^4) if E = O(V^2)

Running original/modified Dijkstra’s V times, once from each vertex
- O(V^3 logV) if E = O(V^2)

Question 3

What DS does Floyd Warshall use?

Answer 3

2D array to store distances

Question 4

Main way Floyd Warshall is used

Answer 4

As a preprocessing step, so that future queries about shortest paths can be answered in O(1) time

Question 5

4 Variants of Floyd Warshall

Answer 5

1. Print the actual SP (uses a predecessor matrix)
2. Transitive closure (find out if i can reach j either directly or indirectly)
3. Minimax / maximin problem
4. Detecting positive / negative cycles