AllPairs ShortestPaths (FloydWarshall Algorithm)
Updated:
1. Basics
The FloydWarshall algorithm is a dynamicprogramming formulation to solve the allpairs shortestpath problem on a directed graph $G = (V, E)$. Same as the BellmanFord algorithm, negativeweight edges may be present in $G$ but still no negativeweight cycle is permitted.
1.1 Similar relaxation process:
Unlike Dijkstra’s algorithm where each edge only gets to be relaxed once, this algorithm presents a relaxation procedure which I think quite resembles that of the BellmanFord algorithm in a sense that they both have about $\mid V \mid$ (outer) iterations in the relaxation process.
1.2 Different structures of the shortest path
The FloydWarshall algorithm considers all the possible intermediate vertices, the “pit stop” mentioned previously, of a simple path.
The algorithm is based upon the following observation. Under the assumption that the vertices of $G$ are $V = { 1, 2, …, n }$, we consider a subset ${ 1, 2, …, k }$ of the vertices for some $k$. For any pair of the vertices $i, j ∈ V$, consider all paths from $i$ to $j$ whose intermediate vertices are all drawn from ${ 1, 2, …, k }$, and let $p$ be a minimumweight path from among them.
Note that we assume path $p$ is simple.
The FloydWarshall algorithm exploits a relationship between path $p$ and shortest paths from i to j with all intermediate vertices in the set ${1, 2, …, k}$.
This relationship depends on whether or not $k$ is an intermediate vertex of path $p$.

[Relationship 1] If $k$ is not an intermediate vertex of path $p$, then all intermediate vertices of path $p$ are in the set ${1, 2,…, k  1}$. Thus, a shortest path from vertex $i$ to vertex $j$ with all intermediate vertices in the set ${1, 2,…, k  1}$ is also a shortest path from $i$ to $j$ with all intermediate vertices in the set ${1, 2,…, k}$.

[Relationship 2] If $k$ is an intermediate vertex of path $p$, then we decompose $p$ into as shown above. By the Lemma 24.1 (in CLRS) , $p_1$ is a shortest path from $i$ to $k$ with all intermediate vertices in the set ${1, 2,…, k}$. Because vertex $k$ is not an intermediate vertex of path $p_1$, we see that $p_1$ is a shortest path from i to k with all intermediate vertices in the set ${1, 2,…, k  1}$. Similarly, $p_2$ is a shortest path from vertex $k$ to vertex $j$ with all intermediate vertices in the set ${1, 2,…, k  1}$.
In a nutshell, the two different relationships represent different decisionmaking processes. In respect of the first relationship, we do not take $k$ into consideration, since it’s not the optimal solution, whilst for the second one we do.
2. Recursive mindset
To take the two relationships elaborated in 1.2 together, we can now construct a recursive solution for this problem as follows:
Tips:
 For $k == 0$, we do the “housekeeping” work, initialization.
 The formula of the case where $k>=1$ clearly illustrates the decisionmaking process based on different relationships that we mentioned in 1.2.
 when $k == 0$, a path from vertex $i$ to vertex $j$ with no intermediate vertex numbered higher than 0 has no intermediate vertices whatsoever.
3. Bottomup DP approach (a better solution)
An implementation of FloydWarshall where the floydwarshall()
function creates a matrix M
that populates the matrix with shortest path information for each vertex:
class Edge:
def __init__(self, start, end, weight):
self.start = start
self.end = end
self.weight = weight
class Graph:
def __init__(self):
# The adjacency matrix that holds the graph data.
self.adj = {}
self.vertex_count = 0
def add_vertex(self, vertex):
if vertex in self.adj:
return "Vertex already exists"
if vertex != self.vertex_count:
return "Don't skip a vertex"
self.adj[vertex] = []
self.vertex_count += 1
def add_edge(self, start, end, weight):
if start not in self.adj:
return "Starting vertex not in graph"
if end not in self.adj:
return "Ending vertex not in graph"
if start == end:
return "Cannot have same start and end vertex"
edge = Edge(start, end, weight)
self.adj[start].append(edge)
def does_edge_exist(self, start, end):
for vertex in self.adj:
for edge in self.adj[vertex]:
if edge.start == start and edge.end == end:
return (True, edge)
return (False, None)
def floydwarshall(self):
import sys
M = [[sys.maxsize for x in range(len(self.adj))] for y in range(len(self.adj))]
for x in range(len(M)):
for y in range(len(M[0])):
if x == y:
M[x][y] = 0
exists, edge = self.does_edge_exist(x, y)
if exists:
M[x][y] = edge.weight
for k in range(len(M)):
for i in range(len(M)):
for j in range(len(M)):
new_distance = M[i][k] + M[k][j]
if new_distance < M[i][j]:
M[i][j] = new_distance
return M
Leave a comment