Navigating the maze

Imagine yourself in the heart of a bustling city, standing at a junction where numerous roads diverge in every direction. You have a destination in mind but are clueless about the optimal route to reach there within this labyrinth of streets and intersections.

This scenario is one example of the fundamental and natural problem of finding the shortest path in a graph, a challenge encountered not only by individuals navigating urban landscapes but also by computer scientists dealing with network optimization, logistics, and routing algorithms.

Unveiling Dijkstra’s algorithm

Named after its creator, Dutch computer scientist Edsger W. Dijkstra, the algorithm serves as a guide in the quest for the shortest path. Its elegance lies in its simplicity and efficiency. Dijkstra’s algorithm solves the single-source shortest path problem in a weighted graph, where each edge has a non-negative weight.

Think of intersections as vertices and roads as edges. An edge’s weight might represent distance, travel time, or another additive cost. The goal is to minimize the sum of those weights along a route.

The algorithm unpacked

1. Initialization. Assign a tentative distance to every vertex. Set the source vertex’s distance to zero and all others to infinity. Add the source to a priority queue.
2. Exploration. While the queue is not empty, choose the vertex with the smallest tentative distance. If the entry is outdated, skip it. Otherwise, explore its neighbors and update their distances whenever a shorter route is found. Add each improved distance to the queue.
3. Retrieval. When the queue is empty, the distance to every reachable vertex is known. Unreachable vertices remain at infinity. To retrieve the actual paths, also record each vertex’s predecessor whenever its distance improves.

Greedy approach and optimality

The key intuition behind Dijkstra’s correctness lies in its greedy strategy: always choosing the vertex with the smallest tentative distance. This approach aims to explore and update the shortest paths incrementally.

At each iteration, the algorithm expands outward from the source. When an unsettled vertex with the smallest tentative distance is removed from the queue, that distance becomes final. Any alternative route through another unsettled vertex must already cost at least as much, and adding non-negative edge weights cannot make it cheaper.

The distinction between tentative and final matters: discovering a vertex does not finalize its distance. A shorter route can still be found before that vertex is selected for processing.

Efficient implementation: priority queue

Integrating a priority queue or heap is a fundamental enhancement in Dijkstra’s algorithm. It prioritizes vertices by their tentative distances, enabling quick access to the vertex with the smallest distance. The algorithm can then explore the most promising vertices without scanning the entire graph at every step.

A binary heap is a practical choice. With a decrease-key operation, Dijkstra’s algorithm runs in O((V + E) log V) time, where V and E are the numbers of vertices and edges.

The Python implementation below uses a simpler alternative: it pushes a new entry whenever a distance improves and skips outdated entries when they are popped. For a simple graph, this also gives the usual O((V + E) log V) bound, though the queue can hold O(E) entries.

A Fibonacci heap supports more efficient amortized decrease-key operations and improves the theoretical bound to O(E + V log V). Its extra complexity means a binary heap is often the simpler implementation choice.

Exploring related algorithms

Breadth-first search (BFS)

BFS explores a graph layer by layer, starting from a source vertex. It finds shortest paths in an unweighted graph, or when all edges have the same non-negative weight. In that setting, minimizing the number of edges also minimizes the path’s total cost.

Bellman–Ford

Unlike Dijkstra’s algorithm, Bellman–Ford handles negative edge weights. It repeatedly relaxes all edges for up to V − 1 passes. A further pass can detect a negative-weight cycle reachable from the source; distances affected by such a cycle have no finite minimum.

Floyd–Warshall

Floyd–Warshall uses dynamic programming to find shortest paths between all pairs of vertices. Its matrix-based approach considers each vertex as a possible intermediate stop. It supports negative edges, but finite shortest paths require that no relevant negative-weight cycle exists. Its O(V³) running time makes it expensive for large graphs.

Johnson’s algorithm

Johnson’s algorithm combines Bellman–Ford and Dijkstra to find all-pairs shortest paths in graphs that may contain negative edges but no negative-weight cycles. It adds a new source with zero-weight edges to every vertex and uses Bellman–Ford to compute potentials. These potentials reweight the original edges to non-negative values while preserving the relative costs of paths with the same endpoints. Dijkstra can then run from each original vertex.

A* search

A* is an informed search algorithm, often used in pathfinding and AI applications. It combines the cost from the source to the current vertex with an estimated cost from that vertex to the target. This heuristic guides the search toward the goal. Optimality depends on the heuristic and implementation: a consistent heuristic supports graph search without reopening settled vertices; with an admissible but inconsistent heuristic, reopening may be necessary.

Python implementation

Here is a Python implementation using an adjacency list and the standard library’s heapq module. As in the original example, vertices are string labels, every vertex appears as a dictionary key, and all weights are non-negative.

import heapq


def dijkstra(graph, start):
    # Initialize all distances to infinity, except the source.
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

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

        # A better route was found after this entry was queued.
        if current_distance > distances[current_vertex]:
            continue

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

    return distances


# Each vertex maps to its neighbors and the edge weights.
graph = {
    'A': {'B': 3, 'C': 5},
    'B': {'A': 3, 'C': 2, 'D': 6},
    'C': {'A': 5, 'B': 2, 'D': 7},
    'D': {'B': 6, 'C': 7}
}

start_vertex = 'A'
shortest_paths = dijkstra(graph, start_vertex)
print(f"Shortest paths from {start_vertex}: {shortest_paths}")

Shortest paths from A: {'A': 0, 'B': 3, 'C': 5, 'D': 9}

This function returns shortest distances, rather than the routes themselves. To reconstruct a route, store predecessor[neighbor] = current_vertex when a distance improves, then follow those predecessors backward from the destination.

Starting at A, we first discover B at distance 3 and C at distance 5. Processing B gives D a tentative distance of 9. Going from B to C also costs 5, so C’s distance stays unchanged. Processing C offers a route to D costing 12, which is worse than 9. The final distance to D is therefore 9.

Replace graph with your own adjacency list to try other examples. Include an empty dictionary for any vertex with no outgoing edges.

For a library implementation, NetworkX’s single_source_dijkstra returns both shortest distances and paths. It is useful when your application already uses NetworkX graph objects.

From intersections to algorithms

Dijkstra’s algorithm is a cornerstone of graph theory and algorithm design. Its simplicity and efficiency make it a useful tool for finding routes through complex networks, whether those networks represent city streets, communication links, or decisions in an optimization problem.

The central idea is small but powerful: keep track of the best distances found so far, always process the closest unsettled vertex next, and use the non-negative edge weights to justify that choice.

So, the next time you find yourself at a crossroads, remember the algorithm that turns a maze of possibilities into a shortest path.

Originally published on Medium. Adapted for this site with clarifications and a worked example.