Graphs

Dijkstra's Algorithm

TimeO((V + E) log V) SpaceO(V + E)

Imagine planning a road trip. From your city, you know the drive time to neighboring cities. You first visit the closest city, then from there update your estimates to its neighbors. You always process the city with the shortest known distance next — greedily expanding your knowledge of shortest routes.

When to use it: Shortest path in a graph with non-negative edge weights. GPS navigation, network routing, or any “minimum cost path” problem with non-negative costs.

Key insight: Once you pop a node from the priority queue, you’ve found the shortest path to it. This greedy property holds because all edge weights are non-negative — no future path can improve a shorter one.

Common trap: Using Dijkstra with negative edge weights. It breaks the greedy guarantee. Use Bellman-Ford instead for graphs with negative weights.

function dijkstra(graph, source):
    dist = {node: infinity for node in graph}
    dist[source] = 0
    priorityQueue = [(0, source)]           # (distance, node)

    while priorityQueue is not empty:
        currentDist, u = priorityQueue.extractMin()

        if currentDist > dist[u]:
            continue                        # skip outdated entry

        for (v, weight) in graph[u]:
            newDist = dist[u] + weight

            if newDist < dist[v]:           # found a shorter path
                dist[v] = newDist
                priorityQueue.insert((newDist, v))

    return dist

import heapq
from collections import defaultdict


def dijkstra(graph: dict[int, list[tuple[int, int]]], source: int) -> dict[int, int]:
    """
    Shortest distances from source to all reachable nodes.
    graph: {node: [(neighbor, weight), ...]}
    """
    dist = defaultdict(lambda: float("inf"))
    dist[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)

        if d > dist[u]:
            continue  # skip stale entry

        for v, weight in graph.get(u, []):
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dict(dist)


def dijkstra_with_path(
    graph: dict[int, list[tuple[int, int]]], source: int, target: int
) -> tuple[int, list[int]]:
    """Returns (shortest_distance, path) from source to target."""
    dist = defaultdict(lambda: float("inf"))
    dist[source] = 0
    prev = {}
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)

        if u == target:
            break

        if d > dist[u]:
            continue

        for v, weight in graph.get(u, []):
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))

    # Reconstruct path
    path = []
    node = target
    while node in prev:
        path.append(node)
        node = prev[node]
    path.append(source)
    path.reverse()

    return dist[target], path

Problem: Given a network of servers with latency on each connection, find the time it takes for a signal to reach all servers from a given starting server.

How would you approach this?

Answer: This is Dijkstra's algorithm. The graph has non-negative weights (latencies). Run Dijkstra from the source server to find shortest paths to all servers. The answer is the maximum of all shortest distances (the last server to receive the signal).

Problem: Given a grid where each cell has a cost to enter, find the path from top-left to bottom-right with the minimum total cost.

How would you approach this?

Answer: This is Dijkstra on a grid. Treat each cell as a node with edges to its neighbors, weighted by the neighbor's cost. Use a min-heap to always expand the cheapest reachable cell next.

Time: O((V + E) log V) using a binary min-heap. Each of the V vertices is extracted from the heap once (O(log V) each), and each of the E edges may trigger a heap insert (O(log V) each). With a Fibonacci heap, this improves to O(V log V + E).

Space: O(V + E) for the distance array, the adjacency list, and the priority queue. The heap may contain up to E entries in the worst case (one per relaxation), though often bounded by V.