Dijkstra vs Bellman-Ford: Key Differences and When to Use Each

The Dijkstra algorithm finds the shortest path efficiently but only works with graphs having non-negative edge weights. The Bellman-Ford algorithm handles graphs with negative edge weights and detects negative cycles but is slower than Dijkstra.

Quick Comparison

Here is a quick side-by-side comparison of the two algorithms based on key factors.

Factor	Dijkstra	Bellman-Ford
Edge Weights	Non-negative only	Supports negative weights
Negative Cycle Detection	No	Yes
Time Complexity	O(V log V + E) with priority queue	O(V * E)
Algorithm Type	Greedy	Dynamic Programming
Use Case	Fast shortest path in positive-weight graphs	Graphs with negative edges or cycle detection
Implementation Complexity	Moderate	Simple

Key Differences

Dijkstra uses a greedy approach that picks the closest unvisited vertex at each step, which makes it very fast for graphs with only non-negative edge weights. It relies on a priority queue to efficiently select the next vertex to process, achieving a time complexity of about O(V log V + E) where V is vertices and E is edges.

In contrast, Bellman-Ford uses dynamic programming by relaxing all edges repeatedly up to V-1 times, allowing it to handle graphs with negative edge weights safely. It can also detect negative weight cycles by checking for further relaxations after V-1 iterations. However, this makes it slower with a time complexity of O(V * E).

Because of these differences, Dijkstra is preferred for speed when negative edges are not present, while Bellman-Ford is chosen for graphs where negative edges or cycle detection is required.

Code Comparison

This example shows how Dijkstra finds the shortest path from a start vertex in a graph with non-negative edges.

python

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]  # priority queue of (distance, vertex)

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Example graph as adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

result = dijkstra(graph, 'A')
print(result)

Output

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Bellman-Ford Equivalent

This example shows how Bellman-Ford finds shortest paths and detects negative cycles in a graph that may have negative edges.

python

def bellman_ford(graph, vertices, start):
    distances = {vertex: float('inf') for vertex in vertices}
    distances[start] = 0

    for _ in range(len(vertices) - 1):
        for u in graph:
            for v, w in graph[u]:
                if distances[u] != float('inf') and distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w

    # Check for negative weight cycles
    for u in graph:
        for v, w in graph[u]:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                return "Graph contains a negative weight cycle"

    return distances

# Example graph with a negative edge
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', -3), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
vertices = ['A', 'B', 'C', 'D']

result = bellman_ford(graph, vertices, 'A')
print(result)

Output

{'A': 0, 'B': 1, 'C': -2, 'D': -1}

When to Use Which

Choose Dijkstra when you need the fastest shortest path solution and your graph has only non-negative edge weights. It is efficient and widely used in routing and navigation systems where negative edges do not occur.

Choose Bellman-Ford when your graph may contain negative edge weights or you need to detect negative weight cycles. It is slower but more versatile, useful in financial modeling or networks where costs can decrease.

Key Takeaways

Use Dijkstra for fast shortest path in graphs without negative edges.

Use Bellman-Ford to handle negative edges and detect negative cycles.

Dijkstra is greedy and faster; Bellman-Ford uses dynamic programming and is slower.

Bellman-Ford can detect negative weight cycles, Dijkstra cannot.

Choose the algorithm based on graph edge weights and performance needs.