Shortest Paths

Choosing the algorithm

Dijkstra's algorithm

Greedy: repeatedly finalize the unvisited node with the smallest tentative distance, then relax its outgoing edges. Correct because with non-negative weights, no later path can make a finalized node closer.

import heapq

def dijkstra(n, adj, src):          # adj[u] = [(v, w), ...]
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                # stale entry (lazy deletion)
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int src) {
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Recovering the path

Store parent[v] = u whenever you relax v through u; walk back from the target.

Early exit

If you only need the distance to one target, return when it's popped (not when pushed).

Dijkstra variants

def minimum_effort_path(heights):            # minimax on a grid
    R, C = len(heights), len(heights[0])
    dist = [[float("inf")] * C for _ in range(R)]
    dist[0][0] = 0
    pq = [(0, 0, 0)]
    while pq:
        d, r, c = heapq.heappop(pq)
        if (r, c) == (R - 1, C - 1):
            return d
        if d > dist[r][c]:
            continue
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C:
                nd = max(d, abs(heights[nr][nc] - heights[r][c]))
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    heapq.heappush(pq, (nd, nr, nc))

0-1 BFS

When every edge weight is 0 or 1, a deque replaces the heap: 0-edges go to the front, 1-edges to the back.

from collections import deque

def zero_one_bfs(n, adj, src):               # adj[u] = [(v, w in {0,1})]
    dist = [float("inf")] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

Bellman-Ford

Relax every edge V − 1 times. After round i, all shortest paths using ≤ i edges are correct. A further improvement on round V means a negative cycle.

def bellman_ford(n, edges, src):             # edges: (u, v, w)
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    for u, v, w in edges:                    # detect negative cycles
        if dist[u] + w < dist[v]:
            return None
    return dist

At most k edges (Cheapest Flights Within K Stops)

Copy the array each round so a round uses only the previous round's values — otherwise one round could chain several edges.

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(k + 1):                   # k stops = k + 1 edges
        new = dist[:]
        for u, v, w in flights:
            if dist[u] + w < new[v]:
                new[v] = dist[u] + w
        dist = new
    return dist[dst] if dist[dst] != float("inf") else -1

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    const int INF = 1e9;
    vector<int> dist(n, INF);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        vector<int> nd = dist;
        for (auto& f : flights)
            if (dist[f[0]] != INF && dist[f[0]] + f[2] < nd[f[1]])
                nd[f[1]] = dist[f[0]] + f[2];
        dist = nd;
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

Floyd-Warshall (all pairs)

DP over allowed intermediate nodes: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). The k loop must be outermost.

def floyd_warshall(n, edges):
    INF = float("inf")
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d                                 # d[i][i] < 0 → negative cycle through i

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Also computes transitive closure (reachability) with booleans — Course Schedule IV.

Shortest paths in a DAG

Relax edges in topological order: O(V + E), works with negative weights, and flipping signs gives the longest path (which is NP-hard in general graphs but easy in DAGs).

A* search (bonus)

Dijkstra with priority g(n) + h(n), where h is an admissible heuristic (never overestimates), e.g. Manhattan distance on a 4-directional grid. It explores far fewer nodes toward a single target. You can compare it with Dijkstra in the visualizer.

Modeling tricks

• State expansion: if the cost depends on more than the node (remaining fuel, stops used, keys held, direction), make the node a tuple. Complexity multiplies by the number of extra states.
• Virtual source: to get distances from many sources, add a fake node with 0-weight edges to all of them (or push them all initially).
• Reverse the graph to compute distances to a target from all nodes.
• Binary search + BFS is an alternative for minimax problems: “can I reach the end using only edges ≤ X?”

Common mistakes

• Using Dijkstra with negative weights.
• Skipping the stale-entry check (d > dist[u]) → slower, and wrong in counting variants.
• Integer overflow when adding to an INT_MAX distance in C++.
• In Bellman-Ford with a hop limit, updating in place instead of from a copy.
• Floyd-Warshall with k not in the outer loop.