USACO Training "Fence Loops" and the Workings of Floyd-Warshall's Algorithm

USACO Training "Fence Loops" and the Workings of Floyd-Warshall's Algorithm

Floyd-Warshall's is an algorithm for computing all-pairs shortest paths, taking a DP approach: selct any "middle node" K and two nodes I and J in which you'd like to calculate the shortest path for, and then define the shortest path between I and J as whichever is smaller, the current shortest path betwen I and J OR the current shortest path between I and K plus the current shortest path between K and J.

At first this may seem obvious. Let's delve into why it works.
If we iterate K from the beginning (1 to N), at any given point in time whilst K is strictly less than a definite number X, we can say that the current shortest path between any two nodes I and J (regardless of whether I=X or J=X) that the current shortest path will NOT include X. The start and end nodes may include X, but no node in between will be X.

The DP approach - 3 parameter version

Of course we need to understand the three-parameter version!

Let D(i, j, k) represent the shortest path between i and j passing only through vertices between 1 and k, inclusive.

Assume that we have an oracle, knowing all the shortest paths.
Let us define D recursively:

Case 1: the shortest path between i and j does not pass through k
The answer will be D(i, j, k-1) since we can shorten the vertice set to between 1 and k-1, inclusive - the shortest path will not pass through k.

Case 2: the shortest path between i and j will pass through k.
Since using Floyd-Warshall's for SP implies there are no negative weight loops, it is optimal to pass through k exactly once. In other words, the shortest path between i and k as well as the shortest path between k and j will not pass through k. Let us cut the shortest path into two shortest paths that share a endpoint k. The length of the shortest path between i and j can be defined as the shortest path between i and k plus the shortest path between k and j. As such, the answer is D(i, k, k-1) + D(k, j, k-1). 

Read full article from USACO Training "Fence Loops" and the Workings of Floyd-Warshall's Algorithm