Shortest Path Algorithms

Analogy categoryAnalogies

Introduction

Shortest path algorithms find the minimum-cost route between vertices in a weighted graph. Dijkstra's algorithm is the standard choice when all edge weights are non-negative, greedily expanding the closest unvisited vertex using a priority queue. When a graph contains negative edge weights, Dijkstra's greedy assumption breaks down, and Bellman-Ford, which relaxes all edges repeatedly, must be used instead — it can also detect negative-weight cycles.

🏏

Cricket analogy: Finding the fastest way for a team to reach a target score through a sequence of overs, where each over has a positive run-cost, is Dijkstra's territory, but if some 'overs' could represent penalty runs to the opponent (negative weight), the greedy approach breaks and you'd need Bellman-Ford to still get it right.

Representation/Syntax

python

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    # graph: dict of node -> list of (neighbor, weight)
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)

    while pq:
        current_dist, node = heapq.heappop(pq)
        if current_dist > dist[node]:
            continue  # stale entry, skip
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

Explanation

Dijkstra's algorithm maintains a min-priority queue keyed by current best known distance. It repeatedly pops the vertex with the smallest tentative distance, and 'relaxes' each outgoing edge — if going through the current vertex offers a shorter path to a neighbor, the neighbor's distance is updated and pushed back into the queue. Because it always expands the closest known vertex first, it never needs to revisit a finalized vertex, which is why it fails with negative weights: a later, cheaper path could still exist through an edge with negative weight. Bellman-Ford instead relaxes every edge V-1 times, guaranteeing correctness even with negative weights, and a V-th pass detects negative cycles if any distance still improves.

🏏

Cricket analogy: Dijkstra's algorithm keeps a priority queue of overs sorted by best known run total, always processing the cheapest over next and updating a batsman's projected score if a shorter route through the current over is found; it never revisits a finalized over, which is why a hidden penalty (negative weight) later would break it, whereas Bellman-Ford relaxes every over V-1 times and a final pass flags a scoring impossibility (negative cycle).

Example

python

def bellman_ford(vertices, edges, start):
    # vertices: list of nodes; edges: list of (u, v, weight)
    dist = {v: float('inf') for v in vertices}
    dist[start] = 0

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

    # Check for negative-weight cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError('Graph contains a negative-weight cycle')

    return dist

graph = defaultdict(list, {
    'A': [('B', 4), ('C', 1)],
    'C': [('B', 2), ('D', 5)],
    'B': [('D', 1)],
    'D': []
})
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

edges = [('A', 'B', 4), ('A', 'C', 1), ('C', 'B', 2), ('B', 'D', 1), ('C', 'D', 5)]
print(bellman_ford(['A', 'B', 'C', 'D'], edges, 'A'))

Complexity

Dijkstra's algorithm with a binary heap runs in O((V + E) log V) time and O(V) space, since each edge relaxation may push a new entry onto the heap. Bellman-Ford runs in O(V * E) time since it performs V-1 rounds of relaxing every edge, making it slower than Dijkstra but strictly more general because it tolerates negative weights and detects negative cycles.

🏏

Cricket analogy: Dijkstra's algorithm with a priority queue processes a match's overs and fielding positions in O((V + E) log V) time and O(V) space, while Bellman-Ford, recalculating every over-to-over link V-1 times, runs in O(V * E) time, slower but able to handle penalty-run scenarios and detect impossible scoring loops that Dijkstra cannot.

Key Takeaways

Dijkstra's algorithm requires non-negative edge weights and runs in O((V+E) log V) with a min-heap.
Bellman-Ford handles negative weights and runs in O(V*E), and can detect negative-weight cycles.
Dijkstra is greedy: it finalizes the closest vertex first and never revisits it.
Bellman-Ford relaxes every edge V-1 times; a further improving pass signals a negative cycle.
Stale priority-queue entries in Dijkstra are safely skipped by comparing against the recorded best distance.

Practice what you learned

1. Why does Dijkstra's algorithm fail on graphs with negative edge weights?

2. What is the time complexity of Dijkstra's algorithm using a binary heap?

3. How many times does Bellman-Ford relax all edges in the main loop?

4. What does an extra Vth relaxation pass in Bellman-Ford that still improves a distance indicate?

5. In the Dijkstra implementation using a heap, why is it safe to skip a popped entry when current_dist > dist[node]?

Was this page helpful?

Graph Traversal: BFS and DFS

Minimum Spanning Tree

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#ShortestPathAlgorithms#Shortest#Path#Algorithms#Representation#StudyNotes#SkillVeris