Floyd-Warshall's Algorithm

This algorithm can be used to solve the all pairs shortest path problem, via dynamic programming. It uses the process of ‘relaxation’ (like Dijkstra’s) to achieve this.

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

Complexity §

Time Complexity: $O(|V{|}^3)$

$O(|V{|}^3)$ for relaxation process + $O(|V|+|E|)$ for initialisation = $O(|V{|}^3)$

Implementation §

Floyd-Warshall.py