Floyd Warshall in Python (with Pseudocode)

Data structures and algorithms are a cornerstone of computer science. In our journey so far, we’ve looked at basic data structures like stacks, queues, and dequeues, linked lists and binary trees, and algorithms like sorting algorithms, tree algorithms, and Dijsktra’s algorithm. Now, let’s take a look at another important graph algorithm – Floyd Warshall.

In this post, we’ll take a look at:

• Floyd Warshall Pseudocode
• Floyd Warshall Algorithm in Python
  • Define Constants and Create Examples
  • Implementing Floyd Warshall in Python
  • Testing Floyd Warshall in Python
• Summary of Floyd Warshall Algorithm in Python

Floyd Warshall Pseudocode

Floyd Warshall is a simple graph algorithm that maps out the shortest path from each vertex to another using an adjacency graph. It takes a brute force approach by looping through each possible vertex that a path between two vertices can go through. 

Let’s take a look at the pseudocode:

1. Pick a vertex – v
2. Calculate distance for each set of vertices
3. If the distance through vertex v is less than the currently recorded distance between two vertices, replace that distance
4. Repeat steps 1 through 3 for each vertex

Note that Floyd Warshall will not work for any graph with negative edge weights. It’s also useless for unweighted and directed graphs.

Floyd Warshall Algorithm in Python

We’re going to implement the Floyd Warshall Algorithm in Python. First we’re going to define any constants we need and create some example adjacency lists, then we’ll define and implement the Floyd Warshall algorithm, finally we’ll test it.

Define Constants and Create Examples

The only constant we need to define for Floyd Warshall is “infinity”. Technically, we could also import the infinity constant from the math module, but the behavior will be the same as long as we define an infinity that is greater than any individual distance between vertices. Most of the time, we won’t be working with graphs with distances of greater than 99999 between vertices so we’ll use that as our infinity value. 

Then we’ll create two examples. These graphs will have 0 in the diagonal since the distance from a point to itself is 0, and we’ll also throw in some infinities into our adjacency graph to represent unconnected vertices.

# define "infinity"
_inf = 99999
 
# example 1
A = [[0, 5, _inf, _inf],
    [50, 0, 15, 5],
    [30, _inf, 0, 15],
    [15, _inf, 5, 0]]
 
# example 2
B = [[0, 3, _inf, 5],
    [2, 0, _inf, 4],
    [_inf, 1, 0, _inf],
    [_inf, _inf, 2, 0]]

These examples should give us:

[0, 5, 15, 10]
[20, 0, 10, 5]
[30, 35, 0, 15]
[15, 20, 5, 0]

and

[0, 3, 7, 5]
[2, 0, 6, 4]
[3, 1, 0, 5]
[5, 3, 2, 0]

Implementing Floyd Warshall in Python

Now that we’ve defined our constant and created our example, we’ll implement the Floyd Warshall algorithm in Python. First, we’ll get the number of vertices that we’re dealing with by getting the length of the graph. Next, we’ll create our loops. 

We need three layers of for loops that will loop through each vertex three times and replace the entry in the graph by the minimum distance between the direct distance between two vertices and the distance between those vertices that goes through the initially defined vertex (in the outermost loop). Finally, we’ll print out the list of lengths for each row in the graph.

# floyd warshall function
def floyd_warshall(graph):
​​   n = len(graph)
   # stepping loop
   for k in range(n):
       # outer loop
       for i in range(n):
           # inner loop
           for j in range(n):
               # replace direct path with path through k if direct path is longer
               graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
   # print complete graph in a pretty manner
   for row in graph:
       print(row)

Testing Floyd Warshall in Python

Now that we’ve implemented the Floyd Warshall algorithm, let’s take a look at how our algorithm does against the expected solutions we saw above. All we do is call Floyd Warshall on each of the graphs we made and check what the solution prints.

print("Shortest Paths Graph for A")
floyd_warshall(A)
print("Shortest Paths Graph for B")
floyd_warshall(B)

We should see an output like the image below.

Summary of Floyd Warshall Algorithm in Python

In this post we went over how to implement Floyd Warshall in Python. We walked through the pseudocode and then the actual implementation. The Floyd Warshall algorithm loops through each vertex three times. First it loops through a chosen vertex, then it loops through sets of two vertices that define the distance between them. While looping, it replaces the distance between two vertices with the minimum between the existing distance and the distance between the chosen vertex.

Further Reading

• Sending API Requests Asynchronously with Python
• Python Generators, Yield, and Yield From
• AI Text Summarizer in Python
• How to Send an Email with an Attachment in Python
• Why Programming is Easy but Software Engineering is Hard

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.