Skip to content
Hello Python

Compute Nonnegative Shortest Paths

Practice ExerciseIntermediateMediumGraphHeapDijkstra

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement dijkstra_distances(node_count, edges, source). Edges are directed [u,v,weight] with nonnegative weights. Return distances, using -1 for unreachable nodes.

Starter code

def dijkstra_distances(node_count, edges, source):
    pass
Test cases

weighted-choice

{
  "args": [
    4,
    [
      [
        0,
        1,
        5
      ],
      [
        0,
        2,
        1
      ],
      [
        2,
        1,
        1
      ],
      [
        1,
        3,
        2
      ]
    ],
    0
  ]
}

Expected: [0,2,1,4]

unreachable

{
  "args": [
    3,
    [
      [
        0,
        1,
        2
      ]
    ],
    0
  ]
}

Expected: [0,2,-1]

Wizard outline
  1. Step 1: Seed one known distance

    Set the source to zero and every other node to unreachable. Dijkstra grows only from a finalized zero-cost source.

  2. Step 2: Relax direct neighbors

    Compute the best one-edge distance from the source. Relaxation is the one state transition Dijkstra repeats.

  3. Step 3: Process the cheapest frontier first

    Repeat relaxation through a min-heap until no better path remains. Nonnegative weights make the smallest frontier distance safe to expand next.

Footguns and prerequisites
  • Dijkstra is invalid with negative weights.
  • Processing stale entries as current can repeat unnecessary work.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Use an adjacency list and min-heap, relaxing an edge only when it improves its endpoint distance.

Why it works: 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.

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]