Dijkstra’s algorithm — shortest path in weighted graph

For non-negative weights. With a binary heap (Python’s heapq): O((V+E) log V).

Setup

import heapq
from collections import defaultdict
from typing import Hashable

# Adjacency list with weights:
# graph[u] = [(weight, neighbor), ...]
graph: dict[Hashable, list[tuple[int, Hashable]]] = defaultdict(list)
for u, v, w in edges:
    graph[u].append((w, v))
    graph[v].append((w, u))   # for undirected

Standard Dijkstra

def dijkstra(graph, start):
    """Returns dict of shortest distances from start to every reachable node."""
    dist = {start: 0}
    heap = [(0, start)]   # (distance, node)
    
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float("inf")):
            continue   # stale entry — already found a better path
        for w, neighbor in graph[node]:
            nd = d + w
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(heap, (nd, neighbor))
    
    return dist

Why the staleness check? Python’s heap doesn’t support decrease_key. When a shorter path is found, we push a new entry instead of updating the old one. The old entry stays in the heap but gets ignored when popped.

Path reconstruction

def dijkstra_with_path(graph, start, target):
    dist = {start: 0}
    prev = {}
    heap = [(0, start)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if node == target: break
        if d > dist.get(node, float("inf")): continue
        for w, neighbor in graph[node]:
            nd = d + w
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                prev[neighbor] = node
                heapq.heappush(heap, (nd, neighbor))
    
    # Reconstruct path
    if target not in dist:
        return None
    path = [target]
    while path[-1] != start:
        path.append(prev[path[-1]])
    path.reverse()
    return dist[target], path

When NOT to use Dijkstra

• Negative weights → Bellman-Ford. Dijkstra’s greedy choice fails when a longer path can become shorter via a negative edge.
• All edges equal weight → BFS is simpler and just as fast.
• All-pairs shortest path on dense graphs → Floyd-Warshall (O(V³)).
• Heuristic available toward target → A* (Dijkstra + heuristic).

A* — Dijkstra with a heuristic

When you have an admissible heuristic h(node) (lower bound on remaining cost), A* prioritizes nodes likely on the optimal path:

import heapq

def astar(graph, start, target, heuristic):
    g_score = {start: 0}
    heap = [(heuristic(start), 0, start)]   # (f, g, node)
    
    while heap:
        f, g, node = heapq.heappop(heap)
        if node == target: return g
        if g > g_score.get(node, float("inf")): continue
        for w, neighbor in graph[node]:
            ng = g + w
            if ng < g_score.get(neighbor, float("inf")):
                g_score[neighbor] = ng
                heapq.heappush(heap, (ng + heuristic(neighbor), ng, neighbor))
    return None

For grid pathfinding: heuristic = Manhattan distance (grid) or Euclidean (continuous).

Heuristic must be admissible (never overestimates) for A* to find optimal paths. Manhattan is admissible on a grid with 4-connectivity.

Bellman-Ford — handles negative edges

For graphs with negative edges (no negative cycles). O(VE):

def bellman_ford(num_nodes, edges, start):
    INF = float("inf")
    dist = [INF] * num_nodes
    dist[start] = 0
    
    for _ in range(num_nodes - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    
    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None   # negative cycle reachable
    
    return dist

Negative cycles are detected on a final iteration (anything still updates → cycle).

Problem: cheapest flights with K stops

import heapq

def find_cheapest_price(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((w, v))
    
    # (cost, node, stops_remaining)
    heap = [(0, src, k + 1)]
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops == 0:
            continue
        for w, neighbor in graph[node]:
            heapq.heappush(heap, (cost + w, neighbor, stops - 1))
    return -1

Pitfalls

• Negative weights with Dijkstra — silent wrong answers. Check the problem.
• Forgetting the staleness check — works but can degenerate to O(V × E log V).
• Off-by-one in stop count — “K stops” usually means K+1 edges; verify with examples.
• Dense graphs — heap-based Dijkstra is O((V+E) log V). For dense (E ~ V²), array-based is O(V²) and faster.
• Heuristic that overestimates in A* — A* gives wrong answers; must be admissible.

Interview angle

• “When does Dijkstra apply, and when does it break?” - non-negative edge weights only. A negative edge invalidates the greedy assumption that the minimum-distance unvisited node is final, so you need Bellman-Ford instead, which also detects negative cycles.
• “Dijkstra or BFS?” - BFS is correct and faster when all edges have equal weight, since it’s Dijkstra with a queue instead of a heap. Reaching for Dijkstra on an unweighted graph is over-engineering.
• “What’s the complexity?” - O((V + E) log V) with a binary heap. Note the lazy-deletion detail: Python’s heapq has no decrease-key, so you push duplicates and skip any popped node already finalised.
• “How do you recover the actual path?” - keep a predecessor map updated whenever you improve a distance, then walk it backwards from the target. Returning only the distance when the question asked for the route is a common miss.