How to Implement Floyd-Warshall Algorithm in Python

Submitted by razormist on Sunday, March 29, 2026 - 23:35.

In this tutorial, we will learn "How to Implement the Floyd–Warshall Algorithm in Python". The main objective is to understand and implement the algorithm effectively. This guide will walk you step by step through the process, making it easy to follow and apply. By the end of this tutorial, you will have a solid understanding of how the Floyd–Warshall Algorithm works in Python, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing the Bellman-Ford Algorithm. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of Python programming.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.

class Graph:
    def __init__(self):
        self.vertices = {}
 
    def add_vertex(self, key):
        vertex = Vertex(key)
        self.vertices[key] = vertex
 
    def get_vertex(self, key):
        return self.vertices[key]
 
    def __contains__(self, key):
        return key in self.vertices
 
    def add_edge(self, src_key, dest_key, weight=1):
        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
 
    def does_edge_exist(self, src_key, dest_key):
        return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
 
    def __len__(self):
        return len(self.vertices)
 
    def __iter__(self):
        return iter(self.vertices.values())
 
 
class Vertex:
    def __init__(self, key):
        self.key = key
        self.points_to = {}
 
    def get_key(self):
        return self.key
 
    def add_neighbour(self, dest, weight):
        self.points_to[dest] = weight
 
    def get_neighbours(self):
        return self.points_to.keys()
 
    def get_weight(self, dest):
        return self.points_to[dest]
 
    def does_it_point_to(self, dest):
        return dest in self.points_to
 
 
def floyd_warshall(g):
    distance = {v: dict.fromkeys(g, float('inf')) for v in g}
    next_v = {v: dict.fromkeys(g, None) for v in g}
 
    for v in g:
        for n in v.get_neighbours():
            distance[v][n] = v.get_weight(n)
            next_v[v][n] = n
 
    for v in g:
        distance[v][v] = 0
 
    for p in g:
        for v in g:
            for w in g:
                if distance[v][w] > distance[v][p] + distance[p][w]:
                    distance[v][w] = distance[v][p] + distance[p][w]
                    next_v[v][w] = next_v[v][p]
 
    return distance, next_v
 
 
def print_path(next_v, u, v):
    if next_v[u][v] is None:
        print("No path", end='')
        return
 
    p = u
    while p != v:
        print(f"{p.get_key()} -> ", end='')
        p = next_v[p][v]
    print(v.get_key(), end='')
 
 
# MAIN PROGRAM
g = Graph()
 
while True:
    print("\n===== Floyd-Warshall Algorithm =====")
    print("Menu")
    print("add vertex <key>")
    print("add edge <src> <dest> <weight>")
    print("floyd-warshall")
    print("display")
    print("quit")
 
    do = input('What would you like to do? ').split()
    if not do:
        continue
 
    operation = do[0]
 
    if operation == 'add':
        suboperation = do[1]
 
        if suboperation == 'vertex':
            key = int(do[2])
            if key not in g:
                g.add_vertex(key)
            else:
                print('Vertex already exists.')
 
        elif suboperation == 'edge':
            src = int(do[2])
            dest = int(do[3])
            weight = int(do[4])
 
            if src not in g:
                print(f'Vertex {src} does not exist.')
            elif dest not in g:
                print(f'Vertex {dest} does not exist.')
            else:
                if not g.does_edge_exist(src, dest):
                    g.add_edge(src, dest, weight)
                else:
                    print('Edge already exists.')
 
    elif operation == 'floyd-warshall':
        distance, next_v = floyd_warshall(g)
        print("\nShortest paths:")
        for start in g:
            for end in g:
                if start != end and distance[start][end] != float('inf'):
                    print(f'From {start.get_key()} to {end.get_key()}: ', end='')
                    print_path(next_v, start, end)
                    print(f' (distance {distance[start][end]})')
 
    elif operation == 'display':
        print('Vertices:', end=' ')
        for v in g:
            print(v.get_key(), end=' ')
        print()
 
        print('Edges:')
        for v in g:
            for dest in v.get_neighbours():
                w = v.get_weight(dest)
                print(f'(src={v.get_key()}, dest={dest.get_key()}, weight={w})')
 
    elif operation == 'quit':
        print("Exiting program...")
        break
 
    else:
        print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to continue? (yes/no): ").strip().lower()
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This Python program provides an interactive implementation of the Floyd-Warshall algorithm for finding shortest paths between all pairs of vertices in a weighted graph. It defines `Graph` and `Vertex` classes to manage the graph structure, where vertices store their neighboring connections and edge weights. The `floyd_warshall` function computes the shortest distances between every pair of vertices and also tracks the path using a helper structure, allowing reconstruction of the actual routes. A `print_path` function is used to display these shortest paths clearly. Through a command-line menu, users can add vertices and edges, display the graph, run the algorithm to view all shortest paths and distances, and exit the program, with input validation to ensure proper graph construction.

Output:

There you have it we successfully created How to Implement Floyd-Warshall Algorithm in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials