Skip to content
Hello Python
Algorithm1 Practice1 Interview

Shortest Path

Compute minimum path cost under edge-weight assumptions that determine the correct method. 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 Shortest Path when the prompt's constraints and required operations match this shape: Compute minimum path cost under edge-weight assumptions that determine the correct method.

Pybit demonstrates Shortest Path in a professional Python interview workspace.
On this page · Match Edge Costs to the Algorithm

Checking your account…

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

Shortest Path Code Labs

Match Edge Costs to the Algorithm

Shortest path is a family of problems. Use BFS for unit edges, Dijkstra for nonnegative weights, Bellman-Ford for possible negative weights, and DAG relaxation when a topological order exists.

Maintain Distance Upper Bounds

A recorded distance is the cheapest path found so far, initially infinity except zero at the source. It becomes final only under the selected algorithm’s proof.

Trace Edge Relaxations

Reference
def relaxation_trace(node_count,edges,start):
    distance=[None]*node_count;distance[start]=0;trace=[]
    for source,target,weight in edges:
        if distance[source] is not None:
            candidate=distance[source]+weight
            if distance[target] is None or candidate<distance[target]:distance[target]=candidate;trace.append(distance.copy())
    return trace
Practice

Implement relaxation_trace(node_count,edges,start). Process weighted directed edges once in order and return distances after every successful relaxation; unreachable is None.

Public tests

  • Improve only through reachable sources

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

Relax Only Through Reachable States

For edge u to v with weight w, propose distance[u] + w only when u is reachable. Replace distance[v] if the candidate is smaller and record predecessor when path reconstruction is required.

Find Unweighted Shortest Paths

Reference
from collections import deque

def unweighted_distances(adjacency,start):
    distance=[-1]*len(adjacency);distance[start]=0;queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in adjacency[node]:
            if distance[neighbor]==-1:distance[neighbor]=distance[node]+1;queue.append(neighbor)
    return distance
Practice

Implement unweighted_distances(adjacency,start). Return shortest edge counts or -1 for unreachable nodes.

Public tests

  • Use first BFS discovery

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

Detect Unreachable and Negative Cases

Use an explicit unreachable sentinel and never add weights to it. Negative edges invalidate Dijkstra’s finalization proof; reachable negative cycles mean no finite shortest distance for affected vertices.

Choose BFS instead of a weighted algorithm for unit edges. Choose Dijkstra for nonnegative weights, Bellman-Ford for possible negative weights, and topological relaxation for a weighted DAG.

Explain It in an Interview

Say: “These edge costs justify this algorithm. Distances are upper bounds, and relaxation improves one through a known reachable prefix.” State directedness, unreachable output, path reconstruction, and the precise complexity for the selected method.

Python Version Note

Complexity & Invariants

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

OperationAverageWorstInterview note
Shortest Path complete workflowO(rows * columns)O(rows * columns)When distance is measured to the nearest of many starts, enqueue all starts at distance zero before expanding one shared BFS. Every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order.

Space

O(rows * columns) for the focused Expand a Multi-Source Frontier implementation.

Assumptions

  • All sources begin at distance zero in one queue. Breadth-first expansion reaches each unvisited neighbor with the smallest possible edge count, and marking on enqueue prevents any longer route from replacing it.
  • 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 Shortest Path 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. When distance is measured to the nearest of many starts, enqueue all starts at distance zero before expanding one shared BFS. Preserve this claim after every transition.
  5. Every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order. Preserve this claim after every transition.

When To Use Or Avoid Shortest Path

Use It When

  • Use Shortest Path 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 Shortest Path 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 multi_source_distances(rows, columns, sources, blocked):
    pass

Use instead

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    blocked_cells = {tuple(cell) for cell in blocked}
    queue = deque()
    for row, column in sources:
        if (row, column) not in blocked_cells and distances[row][column] == -1:
            distances[row][column] = 0
            queue.append((row, column))
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and (nr, nc) not in blocked_cells and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1
                queue.append((nr, nc))
    return distances

Where you will hit this: Expand a Multi-Source Frontier(opens in a new tab)

Breaking the state transition

Starts from only the first source and ignores both additional sources and blocked cells.

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

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    if not sources: return distances
    queue = deque([tuple(sources[0])])
    distances[sources[0][0]][sources[0][1]] = 0
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1; queue.append((nr, nc))
    return distances

Use instead

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    blocked_cells = {tuple(cell) for cell in blocked}
    queue = deque()
    for row, column in sources:
        if (row, column) not in blocked_cells and distances[row][column] == -1:
            distances[row][column] = 0
            queue.append((row, column))
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and (nr, nc) not in blocked_cells and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1
                queue.append((nr, nc))
    return distances

Where you will hit this: Expand a Multi-Source Frontier(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(rows * columns).

Avoid

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    if not sources: return distances
    queue = deque([tuple(sources[0])])
    distances[sources[0][0]][sources[0][1]] = 0
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1; queue.append((nr, nc))
    return distances

Use instead

from collections import deque

def multi_source_distances(rows, columns, sources, blocked):
    distances = [[-1] * columns for _ in range(rows)]
    blocked_cells = {tuple(cell) for cell in blocked}
    queue = deque()
    for row, column in sources:
        if (row, column) not in blocked_cells and distances[row][column] == -1:
            distances[row][column] = 0
            queue.append((row, column))
    while queue:
        row, column = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, column + dc
            if 0 <= nr < rows and 0 <= nc < columns and (nr, nc) not in blocked_cells and distances[nr][nc] == -1:
                distances[nr][nc] = distances[row][column] + 1
                queue.append((nr, nc))
    return 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.