Floyd-Warshalls Algorithm

A continuation to Warshalls Algorithm.
Read Transitive Closure if lacking background.

In Warshall's, we were only concerned with if the node is reachable. Reachability was simply marked by a boolean.

This algorithm is for weighted graphs, and it does the job of Warshalls Algorithm with weights.
It answers the question of the "shortest path" between nodes $a$ and $b$ .

It is the same, DP like algorithm that we have seen before, except now, the psuedo-code is somewhat transformed

Initialization

D[i][j] = 0        if i == j
D[i][j] = weight   if edge exists
D[i][j] = ∞        otherwise

Where {cpp}D represents the equivalent of adjacency matrix, but with distances.
Initially {cpp}D is the same as the adjacency matrix, where each edge is replaced by it's weight instead of a boolean {cpp}true.

Update step :

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Note

Negative weights are fine in this algorithm. It will be considered as usual.

Negative cycles

While in this algorithm we start with {cpp}D[i][i] = 0; meaning that each node is connected to itself with a 0 weight,
If after the run-time of the algorithm {cpp}D[i][i] < 0, that means that there is a negative cycle connecting that node to itself.
Mathematically, it collapses the premise of shortest path between the node and itself, since looping over the same path will reduce the cost of the path again.