1
Q
How to solve APSP problem using SSSP solution for unweighted graph? + Time Complexity
A
Running BFS from each vertex. O(V^3) if E = O(V^2)
2
Q
How to solve APSP problem using SSSP solution for weighted graph? + Time Complexity (2 ways)
A
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)
3
Q
What DS does Floyd Warshall use?
A
2D array to store distances
4
Q
Main way Floyd Warshall is used
A
As a preprocessing step, so that future queries about shortest paths can be answered in O(1) time
5
Q
4 Variants of Floyd Warshall
A
- Print the actual SP (uses a predecessor matrix)
- Transitive closure (find out if i can reach j either directly or indirectly)
- Minimax / maximin problem
- Detecting positive / negative cycles
