🚓 Floyd-Warshall

Shortest Path Problem §

Find the shortest path between all pairs of vertices in weighted graph .

Theory §

Each between two vertices contains at most internal vertices (not including its endpoints), so we can incrementally build this path over many iterations. Such a path would take at most iterations to construct since we find in the first iteration, then , and so on.

Implementation §

def floyd_warshall(adj):
	dist = [[float('inf') for _ in range(len(adj))] for _ in range(len(adj))]
	for u in adj:
		for v, w in adj[v]:
			dist[u][v], dist[v][u] = w, w
	for k in range(len(adj)):
		for i in range(len(adj)):
			for j in range(len(adj)):
				if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

Runtime §

We perform a triple-nested loop over the vertices, giving us .