Dijkstra's Algorithm

Dijkstra's algorithm is a fundamental graph search algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It is crucial for applications like network routing and mapping services where finding optimal paths is essential.

How Dijkstra's Algorithm Works

Initialization

The algorithm begins by setting the distance from the source node to itself as zero. For all other nodes in the graph, their initial distances are set to infinity, indicating that they are currently unreachable. A priority queue is used to store nodes, ordered by their current shortest distance from the source.

Iterative Expansion

The core of Dijkstra's algorithm is an iterative process. In each step, the node with the smallest known distance from the source that has not yet been visited is extracted from the priority queue. This node is considered "settled" because its shortest path from the source has been found.

Edge Relaxation

Once a node `u` is settled, the algorithm examines all its outgoing edges to neighboring nodes `v`. For each neighbor, it calculates a potential new distance to `v` by adding the edge weight `w` to the settled distance of `u`. If this new path (`dist[u] + w`) is shorter than the current known distance to `v` (`dist[v]`), then `dist[v]` is updated, and `v` is added or re-prioritized in the priority queue with its new, shorter distance.

This process continues until the priority queue is empty, meaning all reachable nodes have been visited and their shortest paths determined.

dijkstra(graph, start_node):
    distances = {node: infinity for node in graph}
    distances[start_node] = 0
    priority_queue = [(0, start_node)]  // (distance, node)

    while priority_queue is not empty:
        current_distance, current_node = extract_min(priority_queue)

        // If we've found a shorter path to current_node already,
        // skip this outdated entry.
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            path_through_current = current_distance + weight

            if path_through_current < distances[neighbor]:
                distances[neighbor] = path_through_current
                add_or_update(priority_queue, (path_through_current, neighbor))

    return distances

Key Takeaways

• Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a weighted graph.
• It requires non-negative edge weights to guarantee correctness.
• The algorithm uses a greedy approach, always exploring the closest unvisited node first.
• A priority queue efficiently manages nodes to visit, ordered by their current shortest distance.
• "Relaxing" edges involves updating a neighbor's distance if a shorter path is found through the current node.