Dijkstra's Algorithm

Algorithms

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

In other words, you want to find the shortest path on a graph from point a to point b and you assume that there are no negative distances on the graph

Set all the vertices to be infinite. This is the same trick that you use when you want to find a minimum. You can set your starting value to the highest double allowed and you probably will be able to find a minimum.

Walk through it

Algorithm

The algorithm maintains a set of vertices whose shortest distances are known and uses a priority queue to select the next vertex to process:

Initialize distances to all vertices as infinite, except the source (distance 0)
Add the source vertex to a priority queue
While the queue is not empty:
- Extract the vertex with minimum distance
- For each neighbor, update the distance if a shorter path is found
- Add the neighbor to the queue if it's not already processed

Time Complexity

With a binary heap priority queue, the time complexity is $O ((V + E) lo g V)$ , where $V$ is the number of vertices and $E$ is the number of edges.

Implementation

import heapq

def dijkstra(graph, start):
    # Initialize distances and priority queue
    distances = {{node: float('inf') for node in graph}}
    distances[start] = 0
    priority_queue = [(0, start)]  # (distance, node)
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # Skip if this distance is not the shortest known distance
        if current_distance > distances[current_node]:
            continue
        
        # Process each neighbor
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # Only update if the new distance is shorter
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example usage
if __name__ == "__main__":
    # Define the graph as an adjacency list with weights
    graph = {{
        'A': [('B', 4), ('C', 2)],
        'B': [('C', 5), ('D', 10)],
        'C': [('D', 3)],
        'D': []
    }}
    
    # Run Dijkstra's algorithm
    start_node = 'A'
    distances = dijkstra(graph, start_node)
    
    # Print results
    print("Dijkstra's Algorithm (starting from {}):".format(start_node))
    for node, distance in distances.items():
        print("Distance to {}: {}".format(node, distance))

Exercises

A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.

Open the Dijkstra's Algorithm exercise set → Compute single-source shortest paths in a graph with non-negative edge weights by maintaining a priority queue of (tentative distance, vertex) pairs, repeatedly extracting the minimum, marking it final, and relaxing its outgoing edges.