Dijkstra's Algorithm

Dijkstra's algorithm is a fundamental graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It efficiently determines the shortest path from a starting node to every other node in the graph, making it crucial for network routing, mapping applications, and more.

How Dijkstra's Algorithm Works

The core idea behind Dijkstra's algorithm is a greedy approach called "relaxation." It iteratively explores the graph, always selecting the unvisited node with the smallest known distance from the source, and then updates the distances of its neighbors.

Initialization

We begin by setting the distance from the source node to itself as zero. All other nodes are initialized with an infinite distance, signifying that they are currently unreachable. A priority queue stores nodes to visit, ordered by their current shortest known distance.

Node Relaxation

The algorithm repeatedly extracts the node `u` with the smallest distance from the priority queue. For each neighbor `v` of `u`, it checks if the path through `u` to `v` is shorter than the currently known shortest path to `v`. If `distance[u] + weight(u, v) < distance[v]`, the algorithm updates `distance[v]` and adds `v` to the priority queue. This process is called relaxation.

Path Discovery

By consistently processing the closest unvisited node, Dijkstra's algorithm ensures that when a node is extracted from the priority queue, its distance is the shortest possible from the source. This prevents revisiting nodes with suboptimal paths and guarantees correctness for graphs with non-negative edge weights.

dijkstra(graph, start):
    dist = initialize distances to infinity, dist[start] = 0
    pq = priority queue, add (0, start)

    while pq is not empty:
        d, u = extract min from pq

        if d > dist[u]: continue  // Already found a shorter path

        for each neighbor v of u with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                add (dist[v], v) to pq

    return dist

Search Completion

The algorithm terminates when the priority queue is empty, meaning all reachable nodes have been visited and their shortest paths from the source have been determined.

Key Takeaways

• Dijkstra's algorithm finds the shortest paths from a single source to all other nodes.
• It requires non-negative edge weights to guarantee correctness.
• The algorithm uses a greedy approach, always processing the closest unvisited node.
• A priority queue is essential for efficiently selecting the next node to visit.
• "Relaxation" is the process of updating neighbor distances if a shorter path is found.