# Floyd-Warshall

Tags CS161Graphs

# The motivation

What if we wanted to find all pairwise shortest path? (APSP)?

We can use $n$﻿ Bellman-Ford steps, which takes $n^2m$﻿ complexity. If there are no negative edges, we can use $n$﻿ steps of djikstra’s algorithm, which takes $n^2\log n + nm$﻿.

If $m \propto n^2$﻿, then BF takes $n^4$﻿ complexity, and Djikstra takes $n^2\log n + n^3$﻿, which is OK but can we just do it in $O(n^3)$﻿ steps, regardless of edge weight sign?

# Implementation

## Substructure

Here, we put on our dynamic programming thinking caps. What sort of subproblem can we design? How about an array $D^{(k)}[i, j]$﻿ that is the shortest path between $i, j$﻿ such that all the vertices between $i, j$﻿ are vertices $1, ... k$﻿.

This actually a little bit counterintuitive. The knee-jerk adaptation is to use bellman-ford but pairwise. In that case, $D$﻿ would be the shortest path such that the number of vertices between $i, j$﻿ are less than $k$﻿. However, you can show to yourself that this yields $O(n^4)$﻿ complexity and is not good.

## What happens at each step

You would initialize $D^{(0)}$﻿ as the weighted adjacency matrix (and non-edges are infinite). This because direct edges have no vertices between them, which satisfies the definition of $D$﻿. Then, you would do the following:

1. Select a pair of nodes $A, C$﻿ (represented as an element in $D$﻿).
1. Try if $A→k→C$﻿ is of lower weight than $A→C$﻿. If you can find one, update the distance in $D$﻿. If not, keep what you have. You can use $A→k$﻿ and $k→C$﻿ as defined in your $D$﻿.

Inductively, it should be easy to show that you keep the inductive definition of $D$﻿ after doing this step.

Much like Bellman-Ford, you can show that you only need $n-1$﻿ steps to complete. In each step, you iterate through $n^2$﻿ pairs of vertices, yielding a final complexity of $O(n^3)$﻿.

• Graphical explanation

## Detecting negative cycles

If there are negative cycles, then $D[v, v] < 0$﻿. Because negative cycles necessairly mean that you can circle back to where you started and be better off.