If you know graph algorithms, you must've heard of Dijkstra, Bellman-Ford, Floyd, and Kruskal-Prim's algorithms. In this blog, I'm going to dive all into these four algorithms. At first I thought of making 4 separate blogs, but then again I decided to keep 4 of them in one blog to be more organized.

However, Let's get started!

Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest path between points on a graph.

Dijkstra's Algorithm for SSSP

In the previous blog on SSSP, we saw that we couldn't find the shortest path by DFS and BFS. They had their own complexities. Dijkstra's algorithm is used when DFS, BFS fails. Here's how this works:

Find minimum path from A → G

We set the starting (in this case, A) point's cost to zero an all other' cost to infinity. The from starting point, we look for candidates to move next.

After A, B and C are the next candidates. We calculate each point's cost by adding the current point's cost to the cost of moving to the next point. If this cost is less than the current node's cost, we update it. For example, 0+2 and 0+5 are less than infinity, so we update B to 2 and C to 5. We then move to the point with the lowest cost, B. The costs from B are B→C: 6, B→D: 1, and B→E: 3. We update D to 3 and E to 5. The next minimum is D, so we move to D. The shortest path from A to D is A→B→D. From D, the only move is to E with a cost of 4. Since 3+4 is greater than 5, we don't update E. Thus, A→C is our path. From C, the cost to F is infinity. Since 5+8 is less than infinity, we update F to 13. Finally, from E, we move to G with a cost of 14.

So, the minimum path from A to G is A→B→E→G.

For A to D, it's A→B→D.

For A to F, it's A→C→F.

NB: The starting point is zero because the distance from the starting point to itself is zero. All other vertices are set to infinity since we don't know their distances from the starting point.

Dijkstra's Implementation Part 1

class Edge: 
    def __init__(self, weight, start_vertex, target_vertex): 
        self.weight = weight 
        self.start_vertex = start_vertex 
        self.target_vertex = target_vertex 

class Node: 
    def __init__(self,name): 
        self.name = name 
        self.visited = False 
        #previous node that came to this node 
        self.predecessor = None 
        self.neighbors = [] 
        self.min_distance = float("inf")

    def __lt__(self, other_node) #lt = less than 
        return self.min_distance < other_node.min_distance

a = Node("A") 
b = Node("B") 
print(a<b)

__lt__ function is going to compare the nodes based on the values we have provided. It's going to check the minimum distance value.

Dijkstra's Implementation Part 2

import heapq

class Edge: 
    def __init__(self, weight, start_vertex, target_vertex): 
        self.weight = weight 
        self.start_vertex = start_vertex 
        self.target_vertex = target_vertex 

class Node: 
    def __init__(self, name): 
        self.name = name 
        self.visited = False 
        self.predecessor = None 
        self.neighbors = [] 
        self.min_distance = float("inf")

    def __lt__(self, other_node):  # Add colon here
        return self.min_distance < other_node.min_distance

    def add_edge(self, weight, destination_vertex): 
        edge = Edge(weight, self, destination_vertex) 
        self.neighbors.append(edge)

# Dijkstra's algorithm
class Dijkstra: 
    def __init__(self): 
        self.heap = []

    def calculate(self, start_vertex): 
        start_vertex.min_distance = 0 
        heapq.heappush(self.heap, start_vertex)
        while self.heap: 
            actual_vertex = heapq.heappop(self.heap)
            if actual_vertex.visited: 
                continue
            for edge in actual_vertex.neighbors:  # Iterate over actual_vertex.neighbors
                start = edge.start_vertex 
                target = edge.target_vertex 
                new_distance = start.min_distance + edge.weight 
                if new_distance < target.min_distance: 
                    target.predecessor = start 
                    target.min_distance = new_distance  # Update the distance
                    heapq.heappush(self.heap, target)  # Push the target into the heap
            actual_vertex.visited = True

    def get_shortest_path(self, vertex): 
        print(f"The shortest path to the vertex is: {vertex.min_distance}")
        actual_vertex = vertex 
        while actual_vertex is not None: 
            print(actual_vertex.name, end=" ")
            actual_vertex = actual_vertex.predecessor

Dijkstra's Algorithm with negative cycle

A path is a negative cycle if: There is a cycle, and the total weight of the cycle is negative.

If there is a negative cycle, Dijkstra's algorithm cannot proceed and cannot detect it. To solve this, we use the Bellman Ford Algorithm, which handles negative cycles successfully.

Bellman Ford Algorithm

If a graph has a negative cycle reachable from the source, there is no cheapest path. The Bellman-Ford algorithm can detect and report negative cycles.

Bellman Ford works same as Dijkstra with a small difference. There's a condition here:

If the distance of destination vertex > (destination of source vertex + weight between source and destination vertex) : update distance of destination vertex to (distance of source + weight between source and destination vertex)

In Dijkstra's, we use a min-heap to process the path with the lowest cost. In Bellman Ford, we process the edges as they are given.

As usual, we will set all nodes to infinity except the starting point. And the iteration will run for V-1 times (number of vertices - 1)

Correction : 2nd iteration → Distance → (3rd row) 2+2* = 4

Final solution

Vertex	Distance from E	Path from E
A	6	E→D→B→A
B	3	E→D→B
C	4	E→D→C
D	2	E→D
E	0	0

Bellman Ford algorithm with negative cycle

If the distance of destination vertex > (distance of source vertex + weight between source and destination vertex): Update distance of destination vertex to (distance of source vertex + weight between source and destination)

In case of Bellman Ford algorithm, we iterate V-1 time. But in this time, if we iterate one more time and if any vertices' edge is changed, then in this case we know we have a negative iteration.

Final Solution

Vertex	Distance from E	Path from E
A	6	E→D→B→A
B	3	E→D→B
C	4	E→D→C
D	2	E→D
E	0	0

Why Bellman Ford runs V-1 times?

A question arises that is - why Bellman Ford algorithm detects negative cycle on Vth iteration, why not in (V-1)th iteration?

Vertices and Paths:
- In a graph with V vertices, the longest path from the source to any other vertex (without cycles) will have at most V-1 edges, as the path cannot visit any vertex more than once.
Relaxation Process:
- The Bellman-Ford algorithm works by relaxing all edges in the graph repeatedly. Relaxing an edge means updating the shortest path estimate to the destination vertex of the edge if a shorter path is found.
Relaxation over V-1 Iterations:
- In the first iteration, the algorithm will correctly find the shortest paths to all vertices that are directly connected to the source.
- In the second iteration, it finds the shortest paths to vertices reachable through one intermediate vertex.
- This process continues until the V-1th iteration, ensuring the shortest path to any vertex is found, considering paths with up to V-1 edges.
Why V-1 is Sufficient:
- Any shortest path in a graph without a cycle will have at most V-1 edges, so the algorithm needs at most V-1 iterations to find the shortest paths to all vertices.
- If the algorithm runs one more iteration (the Vth iteration), it can detect negative weight cycles. If any distance is updated during this extra iteration, it shows a cycle where the total weight can keep decreasing indefinitely.

Conclusion:

The Bellman-Ford algorithm runs V-1 times to ensure the shortest paths are found for all vertices, considering paths with up to V-1 edges. The Vth iteration checks for negative-weight cycles, which is why the algorithm stops after V-1 iterations unless checking for these cycles.

Bellman Ford in Python

class Graph: 
    def __init__(self, vertices): 
        self.v = vertices 
        self.graph = [] 
        self.nodes = [] 

    def add_edge(self, source, destination, weight): 
        self.graph.append([source, destination, weight]) 

    def add_node(self, value): 
        self.nodes.append(value)

    def print_solution(self, dist): 
        print("Vertex distance from source:") 
        for key, value in dist.items(): 
            print(key, ':', value)

    def bellman_ford(self, src): 
        dist = {i: float("inf") for i in self.nodes}  #O(V)
        dist[src] = 0

        # Relax all edges V-1 times
        for _ in range(self.v - 1): #O(V)
            for source, destination, weight in self.graph: #O(E)
                if dist[source] != float("inf") and dist[source] + weight < dist[destination]: 
                    dist[destination] = dist[source] + weight

        # Check for negative-weight cycles
        for source, destination, weight in self.graph: #O(E)
            if dist[source] != float("inf") and dist[source] + weight < dist[destination]:
                print("Graph contains a negative weight cycle")
                return

        # Print solution if no negative cycle is found
        self.print_solution(dist)

g = Graph(5) 
g.add_node["A"]
g.add_node["B"]
g.add_node["C"]
g.add_node["D"]
g.add_node["E"]
g.add_edge["A", "C", 6]
g.add_edge["A", "D", 6]
g.add_edge["B", "A", 3]
g.add_edge["C", "D", 1]
g.add_edge["D", "C", 2]
g.add_edge["D", "B", 1]
g.add_edge["E", "B", 4]
g.add_edge["E", "D", 2]
g.bellman_ford("E")

Time Complexity: O(V x E)
Space Complexity: O(V + E)

This accounts for processing all edges V-1 times and storing the graph and distances.

Floyd Warshall Algorithm

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph. It's useful for graphs with negative weights, as it can handle them, unlike some other shortest path algorithms.

Let's say we have a graph like this and we want to find all pairs shortest path in this graph using FW, means we need to find minimum path from each vertex from this graph.

The first step is to create a matrix. Here some of them are zero, some of them are infinity. Zero indicates the source and destination vertex are same. Infinity indicates that right now we don't know if there's a path between these vertices also, there are no direct path between them. The rest are filled with current edge values.

In FW we are going to update the values of the matrix until we find the shortest path. There's a method for doing this

The following is : Via A (1st iteration)

The following is : Via B (2nd iteration)

The following is : Via C (3rd iteration)

4th Iteration (via D)

This is the final result after doing all four iterations. So basically, the idea is we run iterations for the number of vertices and for each vertex.

Why we need Floyd Warshall Algorithm?

We have iterated all the edges V times. As we have seen, FW algorithm results in optimum solution, but how do we know that it really gives the optimum solution? To understand it we need to clarify how many possible ways that we have to find the distance between two source and vertices. With any given node there can be only three possible way to find distance between them.

The vertex is not reachable
Two vertices are directly connected (This is the best solution. It can be improved via other vertex)
Two vertices are connected via other vertex.

For the first option, if there's a vertex E with no edges to other vertices, E as the source node will always be infinity. Running FW here is pointless. For the third option, B→C is a direct connection, but B→C isn't. We need to visit A to go from B to C.

All these cases are considered when performing the FW algorithm. This ensures that the Floyd Warshall algorithm answers the correct one.

Floyd Warshall with negative cycle

The cycle is ABCA

To go through cycle we need to go via negative cycle participating vertex at least twice
FW never runs loops twice via vertex
Hence, FW can never detect a negative cycle

Floyd Warshall in Python

INF = 9999
def printSolution((nV, distance): 
    for i in range(nV): 
        for j in range(nV): 
            if (distance[i][j] == inf): 
                print("INF", end = " ") 
            else: 
                print(distance[i][j], end = " ") 
        print(" ")
def floydWarshall(nV, G): 
    distance = G #O(1)
    for k in range(nV): #O(V)
        for i in range(nV): #O(V)
            for j in range(nV): #O(V)
                distance[i][j] = min(distance[i][j], distance[i][k],distance[k][j])
    printSolution(nV, distance)

G = [ [0, 8, INF, 1], 
       [INF, 0, 1, INF], 
       [4, INF, 0 , INF], 
       [INF, 2, 9, 1]
       ]
floydWarshal(4, G)

Time complexity: O(v^3), Space complexity: O(V)

Kruskal and Prim's Algorithms

Oops! To understand Kruskal and Prim's algorithms, you need to know about Minimum Spanning Tree (MST) and Disjoint Sets. If you already know them, great! If not, don't worry! I have a separate 2-minute blog on MST. Make sure to read it before moving on!

Minimum Spanning Tree (Disjoint Set)

Kruskal Algorithm

Kruskal's algorithm finds the minimum spanning tree for weighted undirected graphs using a greedy approach. It seeks the best solution at each step. (I'll write a separate blog on the Greedy algorithm, but remember Kruskal's follows the same principles.)

Add increasing cost edges at each step
Avoid any cycle at each step.

Choose the first minimum value, then the second, and the third, ensuring the third does not form a cycle. Why do we avoid cycle? Because our final answer must be a tree. Continue this way. This is how Kruskal algorithm works.

This is the pseudocode for Kruskal algorithm.

we have created V numbers of sets. SO it will take O(V) times complexity.
In the next like, we have ordered them. Ordering edges takes O(eloge) time complexity.
Union takes O(V) times complexity

Time complexity: O(v + eloge + ev) = O(elog(e))

Space complexity : O(v+e)

Kruskal Algorithm in Python

As you may recall, we created a disjoint set in the MST blog. We will import it here. (Ensure this file is in the same directory as the Kruskal algorithm file. Otherwise, it might cause problems.)

follow this diagram while coding

import DisjointSet as dst

class Graph: 
    def __init__(self, vertices): 
        self.V = vertices 
        self.graph = [] 
        self.nodes = [] 
        self.MST = [] 

    def addEdge(self, s, d, w): 
        self.graph.append([s, d, w])

    def addNode(self, value): 
        self.nodes.append(value) 

    def printSolution(self): 
        for s, d, w in self.MST: 
            print(f"{s} - {d}: {w}") 

    def kruskalAlgo(self): 
        i, e = 0, 0 
        ds = dst.DisjointSet(self.nodes) 
        self.graph = sorted(self.graph, key=lambda item: item[2]) 
        while e < self.V - 1: 
            s, d, w = self.graph[i] 
            i += 1
            x = ds.find(s)
            y = ds.find(d) 
            if x != y: 
                e += 1 
                self.MST.append([s, d, w])
                ds.union(x, y) 
        self.printSolution()

g = Graph(5)
g.addNode("A")
g.addNode("B")
g.addNode("C")
g.addNode("D")
g.addNode("E")
g.addEdge("A", "B", 5)
g.addEdge("A", "C", 13)
g.addEdge("A", "E", 5)
g.addEdge("B", "A", 5)
g.addEdge("B", "C", 10)
g.addEdge("B", "D", 8)
g.addEdge("C", "A", 13)
g.addEdge("C", "B", 10)
g.addEdge("C", "E", 20)
g.kruskalAlgo()

Prim's Algorithm

Prim's algorithm is like a greedy algorithm. We start with a small part of the problem, solve it, then keep adding more inputs and solving them until we have the solution to the entire problem.

It finds a minimum spanning tree for weighted undirected graphs in following ways:

Choose any vertex as the source, set its weight to 0, and set all other vertices' weights to infinity.
For each adjacent vertex, if its weight is more than the current edge, update it to the current edge.
Mark the current vertex as visited.
Repeat these steps for all vertices in increasing order of weight.

The adjacent vertices of A are B and C, both initially having infinite weight. From A to B, the weight is 20 units, so we update B's weight to 10. We update C's weight to 20. We mark A as visited and continue with the best solution. Next, among B(10), D(inf), C(20), E(inf), B is the best, so we proceed to B. After updating B's adjacent vertices, we look for the next best vertex, which is D. We repeat this process until we reach C, where all adjacent vertices are already visited.

Prim's Algorithm in Python

import sys
class Graph: 
    def __init__(self, vertexNum, edges, nodes): 
        self.edges = edges 
        self.vertexNum = vertexNum 
        self.nodes = nodes 
        self.MST = [] 

    def printSolution(self): 
        print("Edge : Weight") 
        for s, d, w in self.MST: 
            print(f"{s} - {d}: {w}") 

    def primsAlgo(self): 
        visited = [0]*self.vertexNum 
        edgeNum = 0 
        visited[0] = True 
        while edgeNum < self.vertexNum - 1 :  #O(V)
            min = sys.maxsize 
            for i in range(self.vertexNum):    #O(V)
                if visited[i]: 
                    for j in range(self.vertexNum):   #O(V)
                        if ((not visited[j]) and self.edges[i][j]): 
                            if min > self.edges[i][j]: 
                                min = self.edges[i][j]
                                s = i 
                                d = j
            self.MST.append((self.nodes[s], self.nodes[d], self.edges[s][d])
            visited[d] = True 
            edgeNum += 1

edges = [[0,10,20,0,0], 
          [10,0,30,5,0],
        [20,30,0,15,6], 
        [0,5,15,0,8], 
        [0,0,6,8,0]] 
nodes = ["A", "B", "C", "D", "E"]
g.primsAlgo()

Time complexity : O(V^3), Space complexity: O(V)

Prim's vs Kruskal

Kruskal:

Concentrates on edges
Finalize edge in each iteration

Kruskal Applications:

Landing cables
TV network
Tour operations
LAN Networks
A network of pipes for drinking water or natural gas
An electric grid
Single-line cluster

Prim's:

Concentrates on vertices
Finalize vertex in each iteration

Prim's Applications:

Network for roads and rail tracks connecting all the cities
Irrigation channels and placing microwave towers
Designing a fiber-optic grid or ICs
Traveling salesman problem
Cluster analysis
Pathfinding algorithm used AI

Comparison of Dijkstra’s, Bellman-Ford, and Floyd-Warshall algorithms

1. Dijkstra’s Algorithm

Purpose: Finds the shortest path from a single source to all other vertices.
Time Complexity: O((V + E) \log V) with a priority queue.
Space Complexity: O(V) for storing distances.
Graph Type: Works only with non-negative edge weights.
Use Case: Efficient for graphs with non-negative weights and when you need the shortest path from one source.

2. Bellman-Ford Algorithm

Purpose: Finds the shortest path from a single source to all other vertices and can detect negative weight cycles.
Time Complexity: (O(V \times E))
Space Complexity: (O(V)) for storing distances.
Graph Type: Works with graphs that may have negative weight edges.
Use Case: Ideal when the graph has negative weights or you need to detect negative cycles.

3. Floyd-Warshall Algorithm

Purpose: Finds the shortest paths between all pairs of vertices.
Time Complexity: (O(V^3))
Space Complexity: (O(V^2)) for storing the distance matrix.
Graph Type: Handles both positive and negative weights but doesn’t work with graphs containing negative weight cycles.
Use Case: Best for dense graphs where all-pairs shortest path calculations are needed.

Summary

Dijkstra is fast but limited to graphs without negative weights.
Bellman-Ford is slower but can handle negative weights and detect negative cycles.
Floyd-Warshall handles all-pairs shortest paths but is less efficient for large graphs.

Mao Mao's Blog