Bellman-ford vs Dijkstra algorithm: How they calculate shortest path?

The Bellman-Ford and Dijkstra algorithms are popular algorithms designed to calculate or find the shortest path in a weighted graph. Moreover, these algorithms differ in their approach and suitable in different scenarios.

Bellman-ford Algorithm

The Bellman-Ford algorithm is a dynamic programming algorithm that can handle graphs with negative weight edges. It iterates through all the edges from the source vertex of the graph and minimize the distance between vertices until it finds the shortest path to any other vertices in the graph.

Time Complexity of Bellman-ford

The algorithm runs in O(V * E) time complexity. Hence, V is the number of vertices & E is the number of edges in the weighted graph.

Distinctive Features of Bellman-ford algorithm

1. Handle weighted graphs with negative weight edges.
2. Detect negative weight cycles in a graph (means detect cyclic graph).
3. It is slower than Dijkstra’s algorithm, especially for dense graphs.
4. Bellman Ford is useful to solve single-source shortest path problem.

Explanation of Bellman-Ford

Here we have a real-word example to show the working of bellman-ford to evaluate the shortest path as well as cycles in a graph.

def bellman_ford(graph, source):
    # Step 1: Initialize distances and predecessors
    distances = {vertex: float('inf') for vertex in graph}
    distances[source] = 0
    predecessors = {vertex: None for vertex in graph}

• Line#1: bellman_ford(graph, source) function takes a graph represented as a dictionary and a source vertex.
• Line#3-4: It initializes the distances dictionary with infinity for all vertices except the source, which is set to 0.
• Line#5: It also initializes the predecessors dictionary with None for all vertices.

    # Step 2: Relax edges repeatedly
    for _ in range(len(graph) - 1):
        for u, edges in graph.items():
            for v, weight in edges.items():
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    predecessors[v] = u

• Line#2: This loop relaxes the edges repeatedly to find the shortest path. It iterates len(graph) - 1 times, which is the maximum number of edges in any shortest path.
• Line#3-4: It loops over each vertex u in the graph and its neighboring vertices v and corresponding edge weights weight.
• Line#5-7: If a shorter path to v is found through u, the distances and predecessors dictionaries are updated.

    # Step 3: Check for negative weight cycles
    for u, edges in graph.items():
        for v, weight in edges.items():
            if distances[u] + weight < distances[v]:
                raise ValueError("Graph contains a negative weight cycle.")

    return distances, predecessors

• Line#2-3: This loop checks for negative weight cycles in the graph. If a shorter path to a vertex v is found after the previous iterations, it means a negative weight cycle exists.
• Line#4-5: In such cases, a ValueError is raised to indicate the presence of a negative weight cycle.
• Line#7: Finally, the distances and predecessors dictionaries are returned.

Now, here we have main program to test the above code:

graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

source = 'A'
distances, predecessors = bellman_ford(graph, source)
# print distances and predecessors
print("Distances:", distances)
print("Predecessors:", predecessors)

Output

Dijkstra’s Algorithm

Dijkstra’s algorithm is a greedy algorithm that finds the shortest path between a source vertex and all other vertices in a graph with non-negative edge weights. It maintains a priority queue (min-heap) of vertices, continuously selects the vertex with the minimum distance from the source, and relaxes its adjacent edges.

The algorithm terminates when it has visited all vertices or when it reaches the target vertex in case of a single-pair shortest path problem.

Time Complexity of Dijkstra’s Algorithm

Dijkstra’s algorithm has O((V + E) log V) time complexity. V shoes the number of vertices while E shows number of edges.

Distinctive Features of Dijkstra’s Algorithm

• Only works for graphs with non-negative edge weights.
• Guarantees the shortest path when all edge weights are non-negative.
• Faster than the Bellman-Ford algorithm, especially for sparse graphs.
• Deliver solution for single-source shortest path problem.

Explanation with coding example

This coding examples shows how Dijkstra’s algorithms work on non-negative edge weighted graphs. We divided the whole code into multiple chunks. Let’s start.

import heapq

def dijkstra(graph, source):
    # Step 1: Initialize distances and predecessors
    distances = {vertex: float('inf') for vertex in graph}
    distances[source] = 0
    predecessors = {vertex: None for vertex in graph}

• Line#3: dijkstra(graph, source) function takes a graph as a Python dictionary & a source vertex.
• Line#5-6: Initializes the distances dictionary with infinity for all vertices except the source, which is set to 0.
• Line#7: Initializing the predecessors dictionary with None for all current vertices.

    # Step 2: Initialize priority queue and visited set
    queue = [(0, source)]
    visited = set()

• Line#2: A priority queue queue is initialized with a tuple containing the distance (initialized as 0) and the source vertex.
• Line#3: The visited set is used to keep track of the vertices that have been visited.

    while queue:
        # Pop vertex with minimum distance from the priority queue
        current_distance, current_vertex = heapq.heappop(queue)

        # Skip if already visited
        if current_vertex in visited:
            continue

        # Mark as visited
        visited.add(current_vertex)

        # Update distances and predecessors for neighboring vertices
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_vertex

                # Add neighbor to the priority queue
                heapq.heappush(queue, (distance, neighbor))

• Line#1: The algorithm enters a while loop as long as there are vertices remaining in the priority queue.
• Line#3: It extracts the vertex with the minimum distance from the priority queue using heapq.heappop(), which pops the vertex with the smallest distance value.
• Line#6-7: If the current vertex has already been visited, it is skipped, as its shortest path has already been determined.
• Line#10: The current vertex is marked as visited by adding it to the visited set.
• Line#13: The algorithm then updates the distances and predecessors for its neighboring vertices.
• Line#14: It calculates the distance for each neighbour by adding the edge weight between the current vertex and the neighbor to the current distance.
• Line#16: If this new distance is smaller than the current distance stored in the distances dictionary for the neighbor, it means a shorter path has been found.
• Line#17-18: In such cases, the distances and predecessors dictionaries are updated with the new distance and current vertex as the predecessor.
• Line#21: Finally, the neighbor is added to the priority queue with its updated distance.

Here we have a test program to validate the above algorithm written in python. Let’s test the above code with a test example of a weighted graph.

graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 2},
    'C': {'A': 3, 'B': 1, 'D': 6},
    'D': {'B': 2, 'C': 6}
}

source = 'A'
distances, predecessors = dijkstra(graph, source)

print("Distances:", distances)
print("Predecessors:", predecessors)

This code will return the distance between vertices and their predecessor vertices.

Output