Data Structures & Algorithms Cheatsheet

Shortest Paths

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Algorithm Selection

Algorithm	Graph	Time	Space	Negative weights
BFS	unweighted	O(V + E)	O(V)	—
0-1 BFS (deque)	weights ∈ {0, 1}	O(V + E)	O(V)	no
Dijkstra (binary heap)	non-negative weights	O((V + E) log V)	O(V)	no
Dijkstra (Fibonacci heap)	non-negative weights	O(E + V log V)	O(V)	no
Bellman-Ford	any weights	O(V · E)	O(V)	yes, detects cycles
SPFA (queued Bellman-Ford)	any weights	O(E) avg, O(V·E) worst	O(V)	yes
DAG shortest path (topo order)	DAG, any weights	O(V + E)	O(V)	yes
Floyd-Warshall	all pairs, any weights	O(V³)	O(V²)	yes, detects cycles
Johnson	all pairs, sparse	O(V·E + V² log V)	O(V²)	yes
A\*	with an admissible heuristic	O(E) best case	O(V)	no

Decision order: unweighted means BFS. Equal weights means BFS. Non-negative weights means Dijkstra. Negative edges means Bellman-Ford. A DAG means topological relaxation, which beats Dijkstra. All pairs on a small V (≤ 400) means Floyd-Warshall.

Dijkstra

Greedy: always finalize the closest unfinalized vertex. Correct only because no edge can later make a finalized distance smaller, which is exactly what negative weights would break.

import heapq
from collections import defaultdict

def dijkstra(n, edges, src):
    """edges: list of (u, v, w) with w >= 0. Returns a distance list."""
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))            # add the reverse for undirected

    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]                    # (distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                   # stale entry, already improved
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def dijkstra_with_path(n, g, src, dst):
    """Same, but reconstruct the route through a parent array."""
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == dst:
            break                      # early exit, single target
        for v, w in g[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(pq, (d + w, v))
    if dist[dst] == INF:
        return INF, []
    path, cur = [], dst
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return dist[dst], path[::-1]

// Java: PriorityQueue of long-encoded (dist, node) or an int[] pair
PriorityQueue<long[]> pq =
    new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
pq.offer(new long[]{0, src});
while (!pq.isEmpty()) {
    long[] top = pq.poll();
    int u = (int) top[1];
    if (top[0] > dist[u]) continue;          // lazy deletion
    for (int[] e : adj.get(u)) {             // e = {to, weight}
        if (dist[u] + e[1] < dist[e[0]]) {
            dist[e[0]] = dist[u] + e[1];
            pq.offer(new long[]{dist[e[0]], e[0]});
        }
    }
}

Lazy deletion is the standard trick. Instead of decrease-key, push a new entry and skip stale pops with if d > dist[u]: continue. That check is not an optimization, without it the loop can do exponential work.

Weighted Variants Of Dijkstra

The same skeleton solves problems where "distance" is not a sum.

def min_effort_path(heights):
    """Minimize the MAXIMUM step along a path. Replace addition with max."""
    rows, cols = len(heights), len(heights[0])
    dist = [[float("inf")] * cols for _ in range(rows)]
    dist[0][0] = 0
    pq = [(0, 0, 0)]
    while pq:
        d, r, c = heapq.heappop(pq)
        if (r, c) == (rows - 1, cols - 1):
            return d
        if d > dist[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:
                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))
    return 0

def max_probability_path(n, edges, probs, start, end):
    """Maximize a product. Negate for the min-heap, multiply instead of add."""
    g = defaultdict(list)
    for (u, v), p in zip(edges, probs):
        g[u].append((v, p))
        g[v].append((u, p))
    best = [0.0] * n
    best[start] = 1.0
    pq = [(-1.0, start)]
    while pq:
        negp, u = heapq.heappop(pq)
        p = -negp
        if u == end:
            return p
        if p < best[u]:
            continue
        for v, w in g[u]:
            if p * w > best[v]:
                best[v] = p * w
                heapq.heappush(pq, (-best[v], v))
    return 0.0

0-1 BFS

When every weight is 0 or 1, a deque replaces the heap and the whole thing runs in O(V + E). Zero-weight edges go to the front, weight-one edges to the back.

from collections import deque

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

This is the right tool for "minimum obstacle removal" and "minimum cost to make a grid path valid" style problems.

Bellman-Ford

Relax every edge V − 1 times. A shortest path uses at most V − 1 edges, so after that many rounds nothing can improve unless a negative cycle exists.

def bellman_ford(n, edges, src):
    """Returns (dist, has_negative_cycle). O(V * E)."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                      # early exit, already stable
    for u, v, w in edges:              # one more pass detects a negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, True
    return dist, False

def cheapest_flight_k_stops(n, flights, src, dst, k):
    """At most k stops means at most k + 1 edges: run exactly k + 1 rounds
    on a SNAPSHOT of dist so one round cannot chain into the next."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        nxt = dist[:]                  # snapshot is essential here
        for u, v, w in flights:
            if dist[u] != INF and dist[u] + w < nxt[v]:
                nxt[v] = dist[u] + w
        dist = nxt
    return -1 if dist[dst] == INF else dist[dst]

The snapshot in the bounded-hops version is the detail people miss. Relaxing in place lets a single round traverse multiple edges, so the hop limit stops being enforced.

Floyd-Warshall

All pairs, in ten lines. The loop order matters: k must be the outermost loop, because it represents "intermediate vertices allowed so far".

def floyd_warshall(n, edges):
    """O(V^3) time, O(V^2) space. Handles negative 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)      # min guards parallel edges
    for k in range(n):                 # k OUTERMOST
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    negative_cycle = any(d[i][i] < 0 for i in range(n))
    return d, negative_cycle

The same triple loop computes transitive closure (replace min and + with or and and) and the minimax path (replace + with max).

DAG Shortest Path And A\*

def dag_shortest_path(n, g, src, topo_order):
    """O(V + E), works with NEGATIVE weights because there are no cycles."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for u in topo_order:
        if dist[u] == INF:
            continue
        for v, w in g[u]:
            dist[v] = min(dist[v], dist[u] + w)
    return dist

def a_star(start, goal, neighbors, h):
    """h must be admissible: never overestimate the true remaining cost.
    With h = 0 this degenerates exactly to Dijkstra."""
    import heapq
    g_score = {start: 0}
    pq = [(h(start), 0, start)]
    while pq:
        _, g_cur, u = heapq.heappop(pq)
        if u == goal:
            return g_cur
        if g_cur > g_score.get(u, float("inf")):
            continue
        for v, w in neighbors(u):
            ng = g_cur + w
            if ng < g_score.get(v, float("inf")):
                g_score[v] = ng
                heapq.heappush(pq, (ng + h(v), ng, v))
    return float("inf")

Negating all weights to find a longest path only works on a DAG. On a general graph the longest simple path is NP-hard.

Gotchas

Dijkstra breaks on negative edges, silently returning wrong distances rather than failing. Negating weights to find a longest path does not fix it either.
The stale-entry check is mandatory. Without if d > dist[u]: continue, the heap grows and the loop reprocesses vertices.
Bounded hops needs a snapshot. In-place relaxation lets one round travel more than one edge.
Floyd-Warshall loop order. Putting k anywhere but outermost gives wrong answers on graphs that need multi-hop improvement.
INF arithmetic overflows. Integer.MAX_VALUE + w wraps negative in Java and C++. Guard with if (dist[u] != INF) or use long and a smaller sentinel like 1e18.
Undirected graphs need both directions added to the adjacency list. A missing reverse edge is the most common wrong-answer cause here.
Early exit is only safe for a single target, and only after the target is popped, not when it is first pushed.
*A\ needs an admissible heuristic.** An overestimating heuristic returns a path, just not the shortest one.
Grid Dijkstra needs a dist grid, not a visited set. A cell can be reached again at a lower cost.