All-Pairs Shortest-Paths (Floyd-Warshall Algorithm)

⚠️ This post was created when I was in high school and is no longer maintained.

1. Basics

The Floyd-Warshall algorithm is a dynamic-programming formulation to solve the all-pairs shortest-path problem on a directed graph $G = (V, E)$. Same as the Bellman-Ford algorithm, negative-weight edges may be present in $G$ but still no negative-weight 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 Bellman-Ford 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 Floyd-Warshall 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 minimum-weight path from among them.

Note that we assume path $p$ is simple.

The Floyd-Warshall 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 decision-making 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 “house-keeping” work, initialization.
• The formula of the case where $k>=1$ clearly illustrates the decision-making 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. Bottom-up DP approach (a better solution)

An implementation of Floyd-Warshall 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