Problem Solving Basis - Floyd Warshall

In dijkstra algorithm, we have seen single source shortest path algorithm. How about multiple sources? In other words, what if we want to know every pairs of shortest paths?

Idea

Suppose that we have V nodes, and want to figure out shortest path of any pair of those nodes, say distance from V_i to V_j.

Then, there can be possibilities as follows:

• directly from V_i to V_j
• take a detour. Our path is V_i to V_k and V_k to V_j

How To

Let the detour node be k.

And we are now dealing with the shortest path from V_i to V_j.

Firstly, V₁ is our detour node. We compare the path distance: V_i to V_j directly and V_i to V₁, and V₁ to V_j

This is our first answer, and will tell the path when V₁ as detour node being considered.

Secondly, V₂ is our detour node. We compare the path distance: minimum distance from the first calculation, and path detouring V₂.

This is our second answer, and will tell the path when V₁, V₂ as detour node being considered.

What would be our next step? V₁, V₂, …, V_k will be considered.

Complexity Analysis

Graph takes V vertices.

• Time: There are V² pairs, and detouring node V times considered, so V³

• Space: V² for adjacency matrix

Template Code

cpp: https://github.com/dongminkim0220/Problem-Solvings/blob/master/templates/cpp/floyd_warshall.cpp

Problems to Solve

• basics: https://www.acmicpc.net/problem/11404