Dijkstra's Algorithm for Interviews: Template and Problems

Dijkstra's algorithm finds the shortest path from one source node to every other node in a graph whose edge weights are all non-negative, by repeatedly taking the closest unsettled node from a min-heap and relaxing its edges. In a coding interview, use it when edges have different costs (times, distances, efforts, probabilities) and you need the cheapest route; it runs in O((V + E) log V) time with a binary heap.

Edsger W. Dijkstra published it in 1959 in "A note on two problems in connexion with graphs" (Numerische Mathematik, volume 1). This guide covers the interview version: a Python template with heapq, a trace, three worked LeetCode problems (743, 1631 and 1514), a comparison with BFS and Bellman-Ford, common bugs and a practice list. Every code block was run in Python with asserts against a Floyd-Warshall or brute-force check before we published it.

When to use Dijkstra's algorithm

• The problem is a graph or grid and asks for a minimum total cost (time, distance, price, effort) from a source.
• Edges or moves have different weights. If every edge costs the same, plain BFS is simpler and faster; see BFS vs DFS.
• All weights are zero or positive. Negative weights rule Dijkstra out.
• The cost of a path only gets worse as you extend it: a sum of non-negative weights, the maximum step along the path, or a product of probabilities between 0 and 1.
• Words like "network delay", "minimum effort", "cheapest", "fastest route" or "maximum probability".

How Dijkstra's algorithm works

1. Set the source's distance to 0 and push (0, source) onto a min-heap.
2. Pop the node with the smallest tentative distance. Because all weights are non-negative, no later path can reach it more cheaply, so its distance is now final ("settled").
3. Relax each outgoing edge: if going through this node gives a neighbor a shorter distance, record it and push the neighbor with the new distance.
4. Repeat until the heap is empty (or until you pop the target, if you only need one destination).

Trace on a small graph

Edges: A→B (1), A→C (4), B→C (2), B→D (5), C→D (1). Source A.

The shortest path to D is A → B → C → D with cost 4, cheaper than the direct-looking A → B → D (6).

The Python template

Python's heapq module is a min-heap, so the smallest (distance, node) tuple comes out first. Python's heap has no "decrease key" operation, so the standard interview approach is lazy deletion: push a new entry whenever a distance improves and skip outdated entries when you pop them.

import heapq

def dijkstra(graph, source):
    # graph: {node: [(neighbor, weight), ...]} with every weight >= 0
    dist = {source: 0}
    parent = {source: None}
    heap = [(0, source)]                 # (distance so far, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                     # stale entry: u was already settled with a shorter distance
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd             # relax the edge u -> v
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent

def path_to(parent, target):
    if target not in parent:
        return []                        # unreachable
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

The parent map lets you rebuild the actual path, a common follow-up after "what is the shortest distance?"

Worked problem 1: Network Delay Time (LeetCode 743)

Network Delay Time (LeetCode 743): a signal starts at node k; edge (u, v, w) means it takes w time to travel from u to v. Return the time for all n nodes to receive it, or -1 if some never do.

The idea: the time a node receives the signal is its shortest distance from k. The answer is the largest of those distances. This version uses the "settle on first pop" style: the first time a node is popped, its distance is final, so it is recorded once.

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                     # already settled
        dist[u] = d                      # first pop of u is its shortest distance
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

Complexity: O(E log E) time, which is O(E log V) because E is at most V², and O(V + E) space for the graph and heap.

Worked problem 2: Path With Minimum Effort (LeetCode 1631)

Path With Minimum Effort (LeetCode 1631): move through a grid of heights from the top-left to the bottom-right cell. A route's effort is the largest height difference between consecutive cells on it. Minimize that.

The idea: treat each cell as a node and each move as an edge. The path cost is max(effort so far, this step) instead of a sum, but it still never decreases as the path grows, so Dijkstra's greedy choice stays valid. Return as soon as you pop the target.

import heapq

def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
    best = [[float('inf')] * cols for _ in range(rows)]
    best[0][0] = 0
    heap = [(0, 0, 0)]                   # (max step so far on this path, row, col)
    while heap:
        effort, r, c = heapq.heappop(heap)
        if (r, c) == (rows - 1, cols - 1):
            return effort
        if effort > best[r][c]:
            continue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                step = abs(heights[nr][nc] - heights[r][c])
                ne = max(effort, step)   # path cost = largest single step, not the sum
                if ne < best[nr][nc]:
                    best[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return 0

Complexity: O(R·C·log(R·C)) time and O(R·C) space for an R by C grid. Binary search on the answer plus BFS, or union-find over edges sorted by weight, also work and are good alternatives to mention.

Worked problem 3: Path with Maximum Probability (LeetCode 1514)

Path with Maximum Probability (LeetCode 1514): each undirected edge has a success probability. Find the most likely path from start to end.

The idea: a path's probability is the product of its edges. Every edge probability is at most 1, so extending a path never increases its probability: the mirror image of "non-negative weights". Use a max-heap (push negated values into heapq) and the same template.

import heapq
from collections import defaultdict

def max_probability(n, edges, succ_prob, start, end):
    graph = defaultdict(list)
    for (a, b), p in zip(edges, succ_prob):
        graph[a].append((b, p))
        graph[b].append((a, p))
    best = [0.0] * n
    best[start] = 1.0
    heap = [(-1.0, start)]               # max-heap via negated probability
    while heap:
        neg_p, u = heapq.heappop(heap)
        p = -neg_p
        if u == end:
            return p
        if p < best[u]:
            continue
        for v, edge_p in graph[u]:
            np_ = p * edge_p             # probabilities only shrink, so the greedy choice holds
            if np_ > best[v]:
                best[v] = np_
                heapq.heappush(heap, (-np_, v))
    return 0.0

Complexity: O(E log V) time, O(V + E) space.

Dijkstra vs BFS vs Bellman-Ford: which shortest-path algorithm?

Why negative weights break it

Take edges A→B (2), A→C (3) and C→B (-2). Dijkstra pops B at distance 2 and settles it, then pops C at 3. The path A→C→B costs 1, but B was already final, so a settle-once implementation like the LeetCode 743 code reports 2. The lazy template above happens to re-relax B here, but with negative edges that re-processing can blow up to exponential time in the worst case. In an interview, say "negative weights means Bellman-Ford."

Common bugs and edge cases

• Using a max-heap by accident. heapq is a min-heap. Push (distance, node) with the distance first, and negate only when you genuinely want the maximum (as in 1514).
• Skipping the stale-entry check. Without if d > dist[u]: continue the answer is still correct but you re-expand nodes and lose the time bound.
• Marking a node visited when you push it. That is a BFS habit. In Dijkstra a node is final only when it is popped.
• Returning early from the wrong place. Return when the target is popped, not when it is first pushed.
• Unreachable nodes. Return -1 (or infinity) when a node never gets a distance, and test a disconnected graph out loud.
• Directed vs undirected. Add both directions for undirected edges (1514 is undirected; 743 is directed).
• Node labels. LeetCode 743 numbers nodes from 1 to n; off-by-one indexing is a common failure.

Complexity summary

The O(V²) array version is the better choice only for very dense graphs where E is close to V². To compare these growth rates visually, try the free Big-O complexity visualizer.

Practice list: 9 Dijkstra problems

Problem numbers and difficulty labels were checked on LeetCode as of October 2026. For the unweighted graph patterns that come before this one, see graph algorithms for coding interviews, and for heap basics see the heap and priority queue pattern.

How to practice explaining Dijkstra out loud

Most candidates can write the loop; fewer can explain why weights must be non-negative or what the stale-entry check is for. Rehearse that explanation. CoPilot Interview's Mock Interview can include coding questions in your chosen language; it reads each question aloud, scores your spoken answer out of 10 with what to fix and a model answer, and coding questions never auto-submit. For a quick practice round with nothing to install, use the browser mock at /ai-mock-interview (113 questions across 9 tracks, including coding), and keep the coding interview cheat sheet nearby.

FAQ

What is Dijkstra's algorithm used for in coding interviews?

It finds the cheapest path from a source to other nodes when edges have different non-negative costs, such as travel times, distances, efforts or probabilities. Typical LeetCode examples are Network Delay Time (743), Path With Minimum Effort (1631) and Path with Maximum Probability (1514).

What is the time complexity of Dijkstra's algorithm?

With a binary heap it is O((V + E) log V) time and O(V + E) space. The simple version that scans an array for the closest node is O(V squared), which is only better for very dense graphs.

Why doesn't Dijkstra's algorithm work with negative weights?

Dijkstra treats a node's distance as final the first time it is popped from the heap. A negative edge found later could make that node cheaper, so the settled value can be wrong. For graphs with negative weights and no negative cycles, use Bellman-Ford.

When should I use BFS instead of Dijkstra?

Use BFS when every edge has the same cost, because the queue already visits nodes in order of distance and runs in O(V + E). If weights are only 0 or 1, use 0-1 BFS with a deque. Use Dijkstra when weights vary and are non-negative.

How do you implement Dijkstra's algorithm in Python?

Use heapq as a min-heap of (distance, node) tuples. Pop the smallest entry, skip it if its distance is larger than the best known one, and relax each edge by pushing (new distance, neighbor) whenever it improves the neighbor's distance.

Who invented Dijkstra's algorithm and when?

Edsger W. Dijkstra published it in 1959 in the paper A note on two problems in connexion with graphs, in the journal Numerische Mathematik, volume 1.