Skip to content
Hello Python
Algorithm1 Practice1 Interview

Dijkstra

Find shortest paths with nonnegative weights by greedily finalizing the nearest unsettled vertex. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Dijkstra when the prompt's constraints and required operations match this shape: Find shortest paths with nonnegative weights by greedily finalizing the nearest unsettled vertex.

Pybit demonstrates Dijkstra in a professional Python interview workspace.
On this page · Finalize the Cheapest Frontier State

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Dijkstra Code Labs

Finalize the Cheapest Frontier State

Dijkstra uses a min-heap of candidate distances. With nonnegative edges, the cheapest non-stale popped distance cannot later be improved and is safe to expand.

Skip Stale Heap Entries

Python heaps do not decrease keys in place. Push improved candidates and skip a pop when its cost differs from the current distance table; otherwise obsolete paths repeat work.

Trace Dijkstra Heap Pops

Reference
import heapq

def dijkstra_pop_trace(adjacency,start):
    distance=[float("inf")]*len(adjacency);distance[start]=0;heap=[(0,start)];trace=[]
    while heap:
        cost,node=heapq.heappop(heap);stale=cost!=distance[node];trace.append([cost,node,stale])
        if stale:continue
        for neighbor,weight in adjacency[node]:
            candidate=cost+weight
            if candidate<distance[neighbor]:distance[neighbor]=candidate;heapq.heappush(heap,(candidate,neighbor))
    return trace
Practice

Implement dijkstra_pop_trace(adjacency,start). Return [distance,node,stale] for each heap pop; edges are [neighbor,nonnegative_weight].

Public tests

  • Identify stale candidate entries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Relax Nonnegative Edges

For every outgoing edge, compare current cost plus weight with the neighbor’s best known distance. Nonnegative weight is the premise that makes heap-order finalization correct.

Compute Nonnegative Weighted Distances

Reference
import heapq

def dijkstra_distances(adjacency,start):
    distance=[None]*len(adjacency);distance[start]=0;heap=[(0,start)]
    while heap:
        cost,node=heapq.heappop(heap)
        if cost!=distance[node]:continue
        for neighbor,weight in adjacency[node]:
            candidate=cost+weight
            if distance[neighbor] is None or candidate<distance[neighbor]:distance[neighbor]=candidate;heapq.heappush(heap,(candidate,neighbor))
    return distance
Practice

Implement dijkstra_distances(adjacency,start). Return shortest costs, using None for unreachable nodes.

Public tests

  • Finalize cheapest available paths

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Dijkstra or Bellman Ford

Use Dijkstra for nonnegative weighted graphs at O((V + E) log V) with a binary heap. Use Bellman-Ford when negative edges may occur and negative-cycle detection matters. Unit weights call for simpler BFS.

Explain It in an Interview

Say: “The heap’s cheapest current entry is final because every undiscovered continuation adds a nonnegative cost. Improved distances create new heap entries; stale ones are skipped.” Cover unreachable nodes and predecessor tracking.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Dijkstra complete workflowO((V + E) log V)O((V + E) log V)Use an adjacency list and min-heap, relaxing an edge only when it improves its endpoint distance.

Space

O(V + E) for the focused Compute Nonnegative Shortest Paths implementation.

Assumptions

  • With nonnegative weights, the smallest non-stale heap distance cannot later be improved by an unsettled path. Every successful relaxation preserves the best known path, so all reachable final distances are shortest.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Dijkstra invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Distances are upper bounds backed by concrete discovered paths.
  3. A finalized distance cannot later be improved under the stated weight assumptions.
  4. Relax outgoing edges from the closest unsettled node. Preserve this claim after every transition.
  5. Ignore stale heap entries. Preserve this claim after every transition.

When To Use Or Avoid Dijkstra

Use It When

  • Use Dijkstra when this precondition is stated or can be proved: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Use it when this maintained state removes repeated work: Distances are upper bounds backed by concrete discovered paths.

Choose Another Tool When

  • Avoid Dijkstra when this precondition is absent: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.

Avoid

def dijkstra_distances(node_count, edges, source):
    pass

Use instead

def dijkstra_distances(node_count, edges, source):
    import heapq
    graph = [[] for _ in range(node_count)]
    for start, end, weight in edges:
        graph[start].append((end, weight))
    distances = [float('inf')] * node_count
    distances[source] = 0
    frontier = [(0, source)]
    while frontier:
        current, node = heapq.heappop(frontier)
        if current != distances[node]:
            continue
        for neighbor, weight in graph[node]:
            candidate = current + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                heapq.heappush(frontier, (candidate, neighbor))
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Compute Nonnegative Shortest Paths(opens in a new tab)

Breaking the state transition

Returns direct edge weights and misses a cheaper multi-edge path.

Prevent it: Preserve this proof obligation: Every recorded distance is a valid path cost, and the method eventually considers every path that could improve it.

Avoid

def dijkstra_distances(n,edges,source):
    out=[-1]*n; out[source]=0
    for u,v,w in edges:
        if u==source: out[v]=w
    return out

Use instead

def dijkstra_distances(node_count, edges, source):
    import heapq
    graph = [[] for _ in range(node_count)]
    for start, end, weight in edges:
        graph[start].append((end, weight))
    distances = [float('inf')] * node_count
    distances[source] = 0
    frontier = [(0, source)]
    while frontier:
        current, node = heapq.heappop(frontier)
        if current != distances[node]:
            continue
        for neighbor, weight in graph[node]:
            candidate = current + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                heapq.heappush(frontier, (candidate, neighbor))
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Compute Nonnegative Shortest Paths(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O((V + E) log V).

Avoid

def dijkstra_distances(n,edges,source):
    out=[-1]*n; out[source]=0
    for u,v,w in edges:
        if u==source: out[v]=w
    return out

Use instead

def dijkstra_distances(node_count, edges, source):
    import heapq
    graph = [[] for _ in range(node_count)]
    for start, end, weight in edges:
        graph[start].append((end, weight))
    distances = [float('inf')] * node_count
    distances[source] = 0
    frontier = [(0, source)]
    while frontier:
        current, node = heapq.heappop(frontier)
        if current != distances[node]:
            continue
        for neighbor, weight in graph[node]:
            candidate = current + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                heapq.heappush(frontier, (candidate, neighbor))
    return [-1 if value == float('inf') else value for value in distances]

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.