Exploring Shortest Path: A Dijkstra Adventure

Problem description : In a smart‑traffic scenario we need the shortest path from a start node start to an end node end in a weighted road‑network represented as an adjacency list, e.g.

{'A': [('B', 4), ('C', 2)], 'B': [('C', 5), ('D', 10)], 'C': [('D', 3)]}

.

Initial intuition : By eyeballing the graph one might guess the path A→C→D with total distance 5, but a systematic algorithm is required for larger graphs.

Story illustration : A greedy monster (GM) and a "super minimum locator" (the algorithm) repeatedly compare distances from the current node to unvisited neighbours, always choosing the smallest tentative distance, updating records, and confirming that the final path A→B→C→D with distance 6 is indeed optimal after exhaustive checks.

Algorithm overview : Dijkstra repeatedly expands the set of nodes with known shortest distances. At each iteration it selects the unprocessed node with the smallest tentative distance, relaxes its outgoing edges, and updates the priority queue. The algorithm works only on graphs with non‑negative edge weights; for negative weights Bellman‑Ford is required.

Step‑by‑step procedure :

Initialization : Create a priority queue, set the start node distance to 0, all others to infinity, and store distances in a dictionary.

Select minimum‑distance node : Pop the tuple (distance, node, path) from the heap; the heap orders by the first element (distance).

Terminate if end reached : Return the current distance and path.

Relax neighbours : For each (neighbor, weight) in graph.get(current_node, []), compute new_distance = current_distance + weight. If new_distance is smaller than the stored distance, update the dictionary and push (new_distance, neighbor, path + [neighbor]) onto the heap.

Repeat until the queue is empty.

Complexity : With a binary heap the time complexity is O((V + E) log V), where V is the number of vertices and E the number of edges.

Python implementation :

import heapq

def dijkstra(graph, start, end):
    priority_queue = []
    heapq.heappush(priority_queue, (0, start, [start]))
    shortest_distances = {node: float('inf') for node in graph}
    shortest_distances[start] = 0
    while priority_queue:
        current_distance, current_node, path = heapq.heappop(priority_queue)
        if current_node == end:
            return current_distance, path
        for neighbor, weight in graph.get(current_node, []):
            distance = current_distance + weight
            if distance < shortest_distances[neighbor]:
                shortest_distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor, path + [neighbor]))
    return float('inf'), []

# Test case
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 5), ('D', 10)],
    'C': [('D', 3)],
    'D': []
}
start = 'A'
end = 'D'

distance, path = dijkstra(graph, start, end)
print(f"Shortest distance from {start} to {end}: {distance}")
print(f"Path: {' -> '.join(path)}")

The code prints the shortest distance and the corresponding path, e.g. Shortest distance from A to D: 5 and Path: A -> C -> D for the initial graph.

Conclusion : Dijkstra's algorithm, powered by a min‑heap priority queue, reliably finds shortest paths in weighted graphs with non‑negative edges, making it suitable for navigation, network routing, and many other real‑world applications.