How Does Dijkstra's Algorithm Work?

Keep a priority queue of candidate distances. Start with the source at distance zero. Repeatedly take the node with the smallest tentative distance, that distance is final, and then relax its outgoing edges to see whether going through that node gives a shorter route to any neighbour.

import heapq


def dijkstra(graph, start):
    distance = {start: 0}
    heap = [(0, start)]
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > distance[node]:
            continue
        for neighbour, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < distance.get(neighbour, float('inf')):
                distance[neighbour] = new_cost
                heapq.heappush(heap, (new_cost, neighbour))
    return distance


graph = {"A": [("B", 1), ("C", 4)], "B": [("C", 2)], "C": []}
print(dijkstra(graph, "A"))

The output shows A at zero, B at one and C at three. The direct edge from A to C costs four, but going through B costs one plus two, which is cheaper.

The mechanism is that the node with the smallest tentative distance is settled first, and once it is settled no later path can improve it, because any alternative route must pass through some node with a distance at least as large and the edge weights are non negative. That is exactly the assumption the algorithm makes, and it is why Dijkstra fails when a negative edge exists.

The trade-off to name is the heap version against the simple array version. With a heap the cost is O of E log V, while the plain array version is O of V squared. The heap version wins for sparse graphs, the array version for small dense ones, and the heap version is what you should reach for in an interview unless the graph is tiny. The other detail is the stale entry check, which skips a popped item whose cost no longer matches the current best, since the heap can hold several entries for the same node.

Replace the heap with a linear scan: at each step, pick the unsettled node with the smallest distance, settle it, and relax its edges. This is the classic array based version.

def dijkstra_simple(graph, start):
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    visited = set()
    while len(visited) < len(graph):
        node = None
        for candidate in graph:
            if candidate not in visited:
                if node is None or distance[candidate] < distance[node]:
                    node = candidate
        if node is None or distance[node] == float('inf'):
            break
        visited.add(node)
        for neighbour, weight in graph[node]:
            if distance[node] + weight < distance[neighbour]:
                distance[neighbour] = distance[node] + weight
    return distance


graph = {"A": [("B", 1), ("C", 4)], "B": [("C", 2)], "C": []}
result = dijkstra_simple(graph, "A")
print(result["A"], result["B"], result["C"])

The outputs are 0, 1 and 3, the same distances the heap version found.

The mechanism is that the inner loop finds the minimum distance among the unsettled nodes, which is the same choice the heap makes, just found by scanning instead of by ordering. Once that node is settled its edges are relaxed, and the loop repeats until every node is settled or only unreachable nodes remain.

The trade-off to name is the complexity. The linear scan for the minimum costs O of V on every round and there are V rounds, so the whole algorithm is O of V squared, which is worse than the heap version's O of E log V whenever the graph is sparse. In exchange, it uses only a set and a dictionary, with no heap to maintain, and it is easier to write out correctly. For a dense graph with many edges, where E is close to V squared, the array version is competitive because the heap operations start to dominate.

Keep a parent map alongside the distance map. Whenever you improve the distance of a neighbour, record the node you came from as its parent. Once the destination is settled, walk the parent chain backwards to recover the path.

import heapq


def shortest_path(graph, start, goal):
    distance = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > distance[node]:
            continue
        if node == goal:
            break
        for neighbour, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < distance.get(neighbour, float('inf')):
                distance[neighbour] = new_cost
                parent[neighbour] = node
                heapq.heappush(heap, (new_cost, neighbour))
    if goal not in distance:
        return None
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    return list(reversed(path)), distance[goal]


graph = {"A": [("B", 1), ("C", 4)], "B": [("C", 2)], "C": []}
print(shortest_path(graph, "A", "C"))

The output is the path A, B, C and the cost 3. The direct edge from A to C costs four, so the route through B is both shorter in hops and cheaper in total.

The mechanism is that the parent map records the last edge of the best known route to each node. Because the parent is always a node that was already settled, following the chain strictly decreases the distance, so the chain terminates at the source, where the parent is None.

The trade-off to name is that the parent map costs one entry per node, which is small, but reconstructing the path is linear in the length of the path. The other subtlety is that the parent can be overwritten: if a node's distance improves more than once, its parent changes, and only the final value is correct. That is why the reconstruction happens after the algorithm has finished rather than during it. There is also a question of ties, since several distinct paths may have the same cost, and you have to decide which one to report.