How to Implement Johnson’s Algorithm in Python

Submitted by razormist on Friday, March 13, 2026 - 23:22.

In this tutorial, we will learn how to program “How to Implement Johnson’s Algorithm in Python.” The main objective is to understand how to implement Johnson’s Algorithm. This tutorial will guide you step by step through the process of implementing Johnson’s Algorithm. By the end of this tutorial, you will have a solid understanding of how Johnson’s 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 simply 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 Johnson’s Algorithm. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of graph algorithms in Python.

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 set_weight(self, dest, weight):
        self.points_to[dest] = weight
 
    def does_it_point_to(self, dest):
        return dest in self.points_to
 
 
def bellman_ford(g, source):
    distance = dict.fromkeys(g, float('inf'))
    distance[source] = 0
 
    for _ in range(len(g) - 1):
        for v in g:
            for n in v.get_neighbours():
                distance[n] = min(distance[n], distance[v] + v.get_weight(n))
 
    return distance
 
 
def dijkstra(g, source):
    unvisited = set(g)
    distance = dict.fromkeys(g, float('inf'))
    distance[source] = 0
 
    while unvisited:
        closest = min(unvisited, key=lambda v: distance[v])
        unvisited.remove(closest)
 
        for neighbour in closest.get_neighbours():
            if neighbour in unvisited:
                new_distance = distance[closest] + closest.get_weight(neighbour)
                if distance[neighbour] > new_distance:
                    distance[neighbour] = new_distance
 
    return distance
 
 
def johnson(g):
 
    g.add_vertex('q')
 
    for v in g:
        if v.get_key() != 'q':
            g.add_edge('q', v.get_key(), 0)
 
    bell_dist = bellman_ford(g, g.get_vertex('q'))
 
    for v in g:
        for n in v.get_neighbours():
            w = v.get_weight(n)
            v.set_weight(n, w + bell_dist[v] - bell_dist[n])
 
    del g.vertices['q']
 
    distance = {}
 
    for v in g:
        distance[v] = dijkstra(g, v)
 
    for v in g:
        for w in g:
            distance[v][w] += bell_dist[w] - bell_dist[v]
 
    return distance
 
 
# MAIN PROGRAM
while True:
 
    print("\n================= Implement Johnson’s Algorithm =================\n")
 
    g = Graph()
 
    print("Menu")
    print("add vertex <key>")
    print("add edge <src> <dest> <weight>")
    print("johnson")
    print("display")
    print("quit")
 
    while True:
 
        do = input("\nWhat would you like to do? ").split()
 
        if len(do) == 0:
            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 == "johnson":
 
            distance = johnson(g)
 
            print("\nShortest distances:")
            for start in g:
                for end in g:
                    print(f"{start.get_key()} to {end.get_key()} 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":
            break
 
        else:
            print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
 
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This program demonstrates how to implement Johnson’s Algorithm in Python to compute the shortest paths between all pairs of vertices in a weighted directed graph. The program defines `Graph` and `Vertex` classes to manage vertices, edges, and weights, allowing users to build a graph interactively by adding vertices and edges through a menu-driven interface. Johnson’s Algorithm works by first adding a temporary vertex and running the Bellman-Ford algorithm to compute vertex potentials and detect negative edge weights. These values are then used to reweight the graph edges so that all weights become non-negative. After reweighting, the program runs Dijkstra’s algorithm from each vertex to calculate the shortest paths efficiently. Finally, the distances are adjusted back to their original values and displayed as the shortest distance between every pair of vertices. The program also includes options to display the graph structure and repeat the process until the user chooses to exit.

Output:

There you have it we successfully created How to Implement Johnson’s 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