Floyd-Warshall's Algorithm

Floyd-Warshall’s algorithm is a modification of Warshall’s algorithm that allows it to be applicable for weighted graphs. It can be used to solve the all-pairs shortest path problem (ASPP) via dynamic programming. It uses the transitive closure of a graph to achieve this.

Does not work on negative cycles!

Negative weights are not necessarily a problem, but negative cycles are. • These trigger arbitrarily low values for the paths involved. • Floyd’s algorithm can be adapted to detect negative cycles (by looking if diagonal values become negative)#todo

Process §

Let $G$ be the graph which we are trying to solve ASPP for.

1. Initialise a square matrix, (using a 2-dimensional array) of size $|V|\times |V|$. Let $W$ be this matrix.
2. Convert $W$ to an weighted adjacency matrix of $G$ by a nested for loop.
   1. For every node $u$ in $G$, loop through every node $v$ in $G$ and if an edge $(u,v)$ with weight $w$ exists, set $W_{u,v}=w$. Else, set it to 0.
3. Return $W$. If $W[u][v]$ is not 0, then there exists a path from $u$ to $v$.

As a recurrence relation, this can be expressed as:

Let $W$ be an adjacency matrix.

$$W_{i,j}^k=\{\begin{array}{ll}{W}_{i,j},& k=0\\ \min (W_{i,j}^{k-1},T_{i,k}^{k-1}+T_{k,j}^{k-1}),& 0<k\le |V|\end{array}$$

Pseudocode §

Algorithm Floyd_Warshall(G):
	dist ← |V| x |V| array
	
	//Initialise the dist matrix
	For vertex v in G do: #O(|V|)
		dist[v][v] ← 0
	End do
	For edge u-v with weight w in G do: #O(|E|)
		dist[u][v] ← w
	End do
	//Relaxation: Find check if a shorter path exist via intermediate path k
	For k from 1 to |V| do: #O(|V|)
		From i from 1 to |V| do: #O(|V|)
			From j from 1 to |V| do: #O(|V|)
				If dist[i][k] + dist[k][j] < dist[i][j] then:
					dist[i][j] ← dist[i][k] + dist[k][j]
				End if
			End do
		End do
	End do
	Return dist
	
End Algorithm

Time Complexity §

The time complexity is easy to comprehend because of a closed for loop. The triple nested for loop evaluates to $\Theta (|V|)$ three times, giving a time complexity of:

$$\Theta (|V|{)}^3=\Theta (|V{|}^3)$$

Case Scenario	Input Description	Growth Function	Asymptotic	Notes
Worst			$\Theta (\Vert V{\Vert }^3)$	Time complexity is same for every case
Average			$\Theta (\Vert V{\Vert }^3)$
Best			$\Theta (\Vert V{\Vert }^3)$

Visualisation §

Implementation §