Thuật toán đường đi ngắn nhấtShortest Path Algorithms

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

“What is the cheapest way to get from A to B?” is the question that graph algorithms are most often hired to answer. Route planning, network routing protocols (OSPF is literally Dijkstra running on every router), currency arbitrage detection, game AI pathfinding, dependency resolution with costs, minimum-edit-distance as a grid path, and the “minimum number of moves” family of puzzle problems are all shortest-path problems wearing different clothes.

There is no single shortest-path algorithm, and the reason is that the problem comes in variants that admit genuinely different techniques:

• Single-source (SSSP) — cheapest path from one vertex to every other vertex. Dijkstra, Bellman-Ford, BFS.
• Single-pair — cheapest path from one specific vertex to one specific vertex. You can run an SSSP algorithm and stop early, or use A*/bidirectional search to prune.
• All-pairs (APSP) — cheapest path between every pair. Floyd-Warshall, or V runs of Dijkstra, or Johnson’s.
• Single-destination — reverse every edge and run SSSP from the destination.

What decides which algorithm you use is almost entirely the edge weights: unweighted, weights in {0, 1}, small integers, arbitrary non-negative reals, or possibly negative. Each restriction buys you a faster algorithm; each relaxation costs you one. The whole of this note is a walk down that ladder.

One structural fact underlies all of it: shortest paths have optimal substructure. If the shortest path from s to t passes through x, then the portion from s to x is itself a shortest s→x path. If it were not, you could splice in the better prefix and improve the whole path — a contradiction. This is what makes the greedy and dynamic-programming formulations below valid, and it is the same property that powers dynamic programming generally.

Everything here assumes you have read ./13-graph-data-structures.md — the representations, BFS, and DFS.

Fundamentals

The relaxation primitive

Every algorithm in this note is built from one operation. Maintain an array dist[] where dist[v] is the best cost to v found so far (an upper bound on the true shortest distance, starting at ∞ for everything but the source). Relaxing an edge (u, v, w) asks whether going through u improves your estimate for v:

def relax(dist, parent, u, v, w):
    """The single primitive behind BFS, Dijkstra, Bellman-Ford and Floyd-Warshall.
    Returns True if the estimate for v improved."""
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u
        return True
    return False

The dist array is only ever lowered, and it is always the length of some real path (never an underestimate), so once it equals the true shortest distance it stays correct. The algorithms differ only in the order in which they relax edges and how they know when to stop:

Distances, parents, and reconstructing the path

Every implementation below returns dist and parent. Keeping parent[v] — the vertex you arrived from on the best path found so far — costs one array and one assignment per successful relaxation, and it is the only way to output the actual route rather than just its length. The parent array forms a shortest-path tree rooted at the source: V−1 edges, one per reachable non-source vertex.

def reconstruct_path(parent, source, target):
    """Follow parent pointers from target back to source. O(path length)."""
    if target != source and parent[target] == -1:
        return []                     # unreachable
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return path

Why shortest paths are simple paths (and when they are not)

If all cycles have non-negative weight, some shortest path between any two vertices is simple — it repeats no vertex — because walking around a cycle can never help. That bounds path length at V−1 edges, which is exactly the number of rounds Bellman-Ford needs.

If a negative-weight cycle is reachable from the source and can reach the target, “the shortest path” is not merely hard to compute — it does not exist. You can go around the cycle again and drive the cost down without bound. Any correct algorithm must therefore either forbid negative cycles by assumption or detect them and say so. This is the fault line that separates Dijkstra from Bellman-Ford.

Key Concepts

BFS — shortest paths on unweighted graphs, O(V + E)

On an unweighted graph (or one where every edge has the same weight), the shortest path is the one with the fewest edges, and plain BFS computes it. The layer structure of BFS is the distance function: everything at BFS depth k is exactly distance k from the source.

from collections import deque


def bfs_shortest_paths(adj, source):
    """Unweighted single-source shortest paths. Time O(V + E), space O(V).

    Nothing beats this on an unweighted graph: Dijkstra would do the same work
    plus O(log V) heap overhead per edge for no benefit whatsoever."""
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[source] = 0
    q = deque([source])

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)

    return dist, parent

Why it is correct: the queue is always sorted by distance, and holds at most two distinct distance values at a time (k and k+1). So the first time a vertex is discovered, it is discovered from a vertex at the minimum possible distance. Formally: BFS is Dijkstra where every key is an integer that increases by exactly one, so a FIFO queue serves as a priority queue for free.

The practical rule: if all weights are equal, use BFS. Reaching for Dijkstra on an unweighted graph is a log V factor of wasted work and a heap you did not need.

Dijkstra’s algorithm — non-negative weights, O((V + E) log V)

Dijkstra’s is the workhorse. It generalizes BFS by replacing the FIFO queue with a priority queue keyed on tentative distance, so the frontier expands in order of cost rather than hop count.

The invariant: when a vertex is extracted from the priority queue with the minimum key, its distance is final. The argument is a greedy exchange: suppose we extract u with key d, and suppose there existed a cheaper path to u. That path must at some point cross from the set of finalized vertices to the unfinalized ones, at some edge (x, y). But then dist[y] ≤ d, so y (not u) would have been extracted, and since all edge weights are ≥ 0, the rest of the path from y to u cannot reduce the total. Contradiction.

Every step of that argument depends on weights being non-negative.

import heapq


def dijkstra(adj, source):
    """Single-source shortest paths with non-negative weights.

    adj[u] is a list of (v, w) pairs with w >= 0.
    Time O((V + E) log V), space O(V + E).
    """
    n = len(adj)
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 0

    pq = [(0, source)]                   # entries are (tentative distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                     # stale entry: we already found u cheaper
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:             # relax the edge (u, v, w)
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))   # "lazy" insert instead of decrease-key

    return dist, parent

Why O((V + E) log V). Each edge can cause at most one push, so the heap holds O(E) entries; each push and pop costs O(log E) = O(log V) (since E ≤ V², log E ≤ 2 log V). Vertices contribute V pops. Total: O((V + E) log V).

The if d > dist[u]: continue line is load-bearing. Python’s heapq has no decrease-key operation, so the standard workaround is to push a new entry every time a distance improves and leave the old, larger entry in the heap as garbage. That stale-entry check is what makes each vertex’s adjacency list get scanned only once. Delete the line and the algorithm still returns correct distances but may rescan adjacency lists repeatedly.

The O(V²) array version genuinely wins on dense graphs: when E ≈ V², O(V²) beats O(V² log V). The Fibonacci heap’s advantage is asymptotic only — its constants are bad enough that a binary heap usually wins on real inputs up to enormous sizes.

Early exit for single-pair queries: if you only need dist[target], break out of the loop the moment you pop target. Its distance is final at that point by the invariant. This is a large saving in practice and costs nothing.

Why Dijkstra breaks on negative edges

This is worth working through rather than memorizing, because “just add a big constant to every weight” is a tempting and completely wrong fix.

Take this graph:

            2
     S ----------> A
     |             ^
     | 3           | -2
     v             |
     B ------------+

The true shortest distances are dist(A) = 1 (via S→B→A, cost 3 + (−2) = 1) and dist(B) = 3.

Now trace the textbook Dijkstra — the variant that maintains a done set and never revisits a finalized vertex:

1. Pop S (key 0). Relax: dist[A] = 2, dist[B] = 3.
2. Pop A (key 2 — the minimum). Mark A finalized at 2. A has no outgoing edges.
3. Pop B (key 3). Relax B→A: 3 + (−2) = 1 < 2 — but A is already finalized, so the improvement is discarded.
4. Output: dist[A] = 2. Wrong. The answer is 1.

The greedy invariant assumed that no later vertex could offer a cheaper route, and a negative edge makes exactly that possible.

The lazy-heap implementation above happens to survive this three-vertex example — it has no done set, so it would re-push A with key 1 and fix the answer. That is not a rescue, it is a trap: on adversarial graphs the lazy version re-pops vertices an exponential number of times (Johnson’s classic construction chains k gadgets to force 2^k pops), and on a graph with a negative cycle it never terminates at all. Do not run Dijkstra on graphs with negative edges.

And do not reweight by adding a constant. Suppose S→T costs 1, S→X costs −2, and X→T costs 2. True answer: S→X→T = 0, cheaper than S→T = 1. Add 2 to every weight to eliminate the negative: now S→T = 3 and S→X→T = 0 + 4 = 4. The direct edge wins. A constant shift penalizes paths in proportion to how many edges they use, so it changes which path is shortest. The correct reweighting is Johnson’s algorithm, which uses Bellman-Ford from a virtual super-source to compute a potential h(v) per vertex and sets w'(u,v) = w(u,v) + h(u) − h(v). That transformation is non-negative and telescopes along any path, so relative path costs are preserved.

0-1 BFS — weights in {0, 1}, O(V + E)

When every edge weight is 0 or 1, you can drop the heap entirely. Use a deque: a 0-weight edge keeps you in the same “layer”, so push to the front; a 1-weight edge advances one layer, so push to the back. The deque stays sorted by distance with at most two distinct values, exactly like a BFS queue.

from collections import deque


def zero_one_bfs(adj, source):
    """Shortest paths when every weight is 0 or 1. Time O(V + E), space O(V).

    adj[u] is a list of (v, w) with w in {0, 1}.
    """
    n = len(adj)
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 0
    dq = deque([source])

    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                if w == 0:
                    dq.appendleft(v)     # same layer -> must be processed first
                else:
                    dq.append(v)         # next layer -> goes behind everything

    return dist, parent

This turns an O(E log V) problem into an O(V + E) one, which matters at scale. The classic use is grid problems with two kinds of move: “walking through an empty cell is free, breaking a wall costs 1 — what is the minimum number of walls to break?” Model the free move as weight 0 and the costly move as weight 1, and 0-1 BFS answers it in a single linear pass.

The generalization to small integer weights 0..C is Dial’s algorithm: keep V·C + 1 buckets indexed by distance and sweep them in order, for O(E + V·C). Worth it when C is tiny; a heap is simpler otherwise.

DAG shortest paths — any weights, O(V + E)

If the graph is a directed acyclic graph, you can do better than Dijkstra even with negative weights: process vertices in topological order and relax each vertex’s outgoing edges once. By the time you reach u, every path into u has already been considered, so dist[u] is final.

def dag_shortest_paths(adj, source, topo_order):
    """Shortest paths on a DAG. Weights may be negative; a DAG has no cycles,
    so negative cycles are impossible. Time O(V + E), space O(V).

    `topo_order` comes from topological sort - see 13-graph-data-structures.md.
    """
    n = len(adj)
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 0

    for u in topo_order:
        if dist[u] == INF:
            continue                     # u is not reachable from source
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    return dist, parent

Negate the weights and you get longest path in a DAG, which is the critical path of a project schedule or a build graph — and which is NP-hard on general graphs but linear here. This is the single most under-used shortest-path algorithm: if your graph is a DAG, use it.

Bellman-Ford — any weights, O(V · E), detects negative cycles

Bellman-Ford abandons greed. It relaxes every edge, V−1 times. After round i, every dist[v] reachable by a path of at most i edges is correct; since a shortest simple path has at most V−1 edges, V−1 rounds suffice.

def bellman_ford(n, edges, source):
    """Single-source shortest paths with arbitrary edge weights.

    `edges` is a list of (u, v, w) triples - the edge-list representation.
    Time O(V * E), space O(V). Raises ValueError on a reachable negative cycle.
    """
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[source] = 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
                parent[v] = u
                changed = True
        if not changed:
            break                        # a full pass changed nothing: we are done

    # One extra pass. If anything still improves, no finite answer exists.
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a reachable negative-weight cycle")

    return dist, parent

Why O(V · E). V−1 rounds times E relaxations each. The early exit (“a full pass changed nothing”) often makes it far faster in practice, but the worst case is real: a path graph with edges supplied in exactly the wrong order needs all V−1 rounds.

Negative-cycle detection is the extra pass. After V−1 rounds every distance is final if no negative cycle exists. So if a V-th round can still improve something, a negative cycle is reachable. This is not a side benefit — it is the reason Bellman-Ford is used in currency arbitrage detection (a negative cycle in −log(exchange rate) space is a risk-free profit loop) and in distance-vector routing protocols like RIP.

To recover the cycle itself rather than just its existence, track which vertex was relaxed in the final round and walk back V parent steps to be certain you have landed inside the cycle:

def find_negative_cycle(n, edges):
    """Return one negative cycle as a list of vertices, or None.

    dist starts at 0 everywhere, which is equivalent to a virtual super-source
    with 0-weight edges to every vertex - this finds a negative cycle anywhere
    in the graph, not only those reachable from a chosen source.
    Time O(V * E).
    """
    dist = [0] * n
    parent = [-1] * n
    x = -1

    for _ in range(n):
        x = -1
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                x = v                    # remember the last vertex improved
        if x == -1:
            return None                  # a full pass with no change: no negative cycle

    # x is on or downstream of a negative cycle. Walking back n parent links
    # is guaranteed to land us on a vertex that is actually in the cycle.
    for _ in range(n):
        x = parent[x]

    cycle = [x]
    cur = parent[x]
    while cur != x:
        cycle.append(cur)
        cur = parent[cur]
    cycle.append(x)
    cycle.reverse()
    return cycle

SPFA (Shortest Path Faster Algorithm) is Bellman-Ford with a queue of “vertices whose distance just changed”, so you only re-relax edges out of vertices that could produce an improvement. It is often dramatically faster on real graphs, but its worst case is still O(V·E) and adversarial inputs are easy to construct — it has been deliberately broken in competitive programming for years. Use it knowing it is a constant-factor optimization, not a complexity improvement.

Floyd-Warshall — all pairs, O(V³)

Floyd-Warshall computes the shortest distance between every pair of vertices with three nested loops and no data structures at all. It is a textbook dynamic program: let d[k][i][j] be the shortest i→j distance using only vertices 0..k−1 as intermediates. Then

d[k][i][j] = min( d[k-1][i][j],                 # do not route through k
                  d[k-1][i][k] + d[k-1][k][j] ) # route through k

and the k dimension can be dropped in place, which is why the real implementation is a 2D array.

def floyd_warshall(n, edges):
    """All-pairs shortest paths. Time O(V^3), space O(V^2).

    Handles negative edges. Raises on a negative cycle (detected as dist[v][v] < 0).
    `nxt[i][j]` is the first hop on a shortest i -> j path, for reconstruction.
    """
    INF = float("inf")
    dist = [[INF] * n for _ in range(n)]
    nxt = [[-1] * n for _ in range(n)]

    for v in range(n):
        dist[v][v] = 0
        nxt[v][v] = v
    for u, v, w in edges:
        if w < dist[u][v]:               # keep the cheapest parallel edge
            dist[u][v] = w
            nxt[u][v] = v

    for k in range(n):                   # k MUST be the outermost loop
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                 # i cannot reach k: skip the whole row
            row_k = dist[k]
            row_i = dist[i]
            for j in range(n):
                if dik + row_k[j] < row_i[j]:
                    row_i[j] = dik + row_k[j]
                    nxt[i][j] = nxt[i][k]

    for v in range(n):
        if dist[v][v] < 0:
            raise ValueError("negative cycle through vertex %d" % v)

    return dist, nxt


def fw_path(nxt, i, j):
    """Reconstruct a shortest path from the `nxt` table. O(path length)."""
    if nxt[i][j] == -1:
        return []
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path

The k loop must be outermost. This is the classic Floyd-Warshall bug: swap the loops and the recurrence no longer guarantees that d[i][k] and d[k][j] are already final when you use them, and you get answers that are too large in ways that look plausible.

When to use it: small dense graphs (V ≤ 400 or so in Python, V ≤ 1000 in C++), when you need all pairs, or when you want transitive closure (replace min/+ with or/and and you have Warshall’s reachability algorithm). For sparse graphs with V large, running Dijkstra from every vertex is O(V(V + E) log V), which beats O(V³) handily — and Johnson’s algorithm does the same with negative edges allowed, by reweighting with Bellman-Ford potentials first.

A* — informed single-pair search

Dijkstra explores in every direction equally, which is wasteful when you know roughly where the goal is. A* adds a heuristic h(v): an estimate of the remaining cost from v to the goal. Instead of prioritizing by g(v) (cost so far), it prioritizes by f(v) = g(v) + h(v) — estimated total cost of the best route through v. The effect is to bias the search towards the goal.

import heapq


def a_star(neighbours, start, goal, h):
    """A* single-pair shortest path.

    neighbours(u) -> iterable of (v, w) with w >= 0
    h(u)          -> estimated remaining cost from u to goal (must be admissible)

    Returns (cost, path). With h identically 0 this is exactly Dijkstra.
    """
    open_heap = [(h(start), 0, start)]   # (f = g + h, g, vertex)
    g_score = {start: 0}
    parent = {start: None}
    closed = set()

    while open_heap:
        f, g, u = heapq.heappop(open_heap)
        if u in closed:
            continue                     # stale entry
        if u == goal:
            path = []
            node = goal
            while node is not None:
                path.append(node)
                node = parent[node]
            path.reverse()
            return g, path
        closed.add(u)

        for v, w in neighbours(u):
            ng = g + w
            if ng < g_score.get(v, float("inf")):
                g_score[v] = ng
                parent[v] = u
                heapq.heappush(open_heap, (ng + h(v), ng, v))

    return float("inf"), []

Two properties of the heuristic decide whether A* is correct:

• Admissible — h(v) never overestimates the true remaining cost: h(v) ≤ d(v, goal) for all v, and h(goal) = 0. An admissible heuristic guarantees A* returns an optimal path (in the tree-search sense, without a closed set).
• Consistent / monotone — h(u) ≤ w(u, v) + h(v) for every edge, and h(goal) = 0. This is the triangle inequality applied to the heuristic. Consistency implies admissibility, and it is what makes the closed set above safe: with a consistent heuristic, f is non-decreasing along any path, vertices are finalized in non-decreasing f order, and a vertex never needs to be reopened.

If your heuristic is admissible but not consistent, the closed set can finalize a vertex too early. The fix is to allow reopening (remove v from closed when a better g is found) — correct, but potentially much slower.

Standard heuristics:

The trade-off is sharp: a larger admissible h prunes more. h ≡ 0 is Dijkstra (correct, slow). h equal to the exact remaining distance would walk straight to the goal (correct, but computing it is the original problem). Real heuristics live between. If you knowingly overestimate — “weighted A*”, using ε · h for ε > 1 — you get a much faster search that returns a path at most ε times optimal, which is often the right engineering trade for a game or a UI.

A* does not improve the worst-case complexity: with a useless heuristic it is exactly Dijkstra, O((V + E) log V). Its value is entirely in the constant factor, and on a continent-scale road graph with a good heuristic that constant factor is orders of magnitude.

A related pruning technique for the single-pair case is bidirectional search: run one search forward from s and one backward from t, and stop when they meet. If the search explores a ball of radius d, two balls of radius d/2 are exponentially smaller in a graph with branching factor b — 2·b^(d/2) instead of b^d. The termination condition is fiddlier than it looks (you cannot stop at the first common vertex; you must stop when the sum of the two frontier keys exceeds the best path found so far), which is why production route planners use it carefully or use contraction hierarchies instead.

Which algorithm to use when

The decision procedure, in order:

1. Are all weights equal? → BFS.
2. Are weights only 0 and 1? → 0-1 BFS.
3. Is the graph a DAG? → topological-order relaxation (works with negative weights too).
4. Any negative weights? → Bellman-Ford (or Johnson’s for all-pairs). Otherwise Dijkstra.
5. Do you need all pairs? → Floyd-Warshall if dense/small, V × Dijkstra if sparse, Johnson’s if sparse and negative.
6. One specific target, and can you estimate remaining distance? → A*.

Best Practices

• Match the algorithm to the weights, not to habit. Dijkstra on an unweighted graph wastes a log V factor; Bellman-Ford where Dijkstra applies wastes a factor of V. Both are common in code review.
• Never run Dijkstra on a graph with negative edges, and never “fix” it by adding a constant. Shifting weights changes which path is shortest, because it charges every path per edge. Use Bellman-Ford, or Johnson’s if you need the reweighting.
• Keep the stale-entry check (if d > dist[u]: continue) in every lazy-heap Dijkstra. Without a decrease-key operation it is what keeps the per-vertex work bounded.
• Break early on single-pair Dijkstra. Popping the target means its distance is final; there is no reason to finish the graph.
• Store parent[] from the start. Adding path reconstruction later means rerunning the algorithm.
• Use float("inf") for unreachable, and guard dist[u] != INF before relaxing. In Bellman-Ford’s edge loop, relaxing from an unreached vertex propagates inf + w, which in Python is inf and harmless, but in a fixed-width integer implementation is an overflow that silently produces small negative distances.
• Put the k loop outermost in Floyd-Warshall. The wrong loop order produces plausible-looking wrong answers, which is the worst kind.
• Check V before reaching for Floyd-Warshall. O(V³) in pure Python is roughly V = 300–400 per second-ish budget; above that, run Dijkstra from each source instead.
• Validate heuristic admissibility before trusting A*. A heuristic that overestimates by even a little gives paths that are silently suboptimal. If you want that trade, make it deliberately (weighted A*) and document the approximation ratio.
• Watch for floating-point weights. Comparing accumulated float distances with < can flip on ties and produce non-deterministic paths. Where possible, scale to integers (milliseconds, centimetres) and stay exact.
• Break ties deterministically. heapq compares the second tuple element when the first ties, so (dist, vertex) gives a stable, reproducible ordering — useful when tests compare exact paths.
• On a grid, remember it is an implicit graph. You rarely need to build an adjacency list; generate neighbours on the fly and key dist by coordinate. See the grid section of ./13-graph-data-structures.md.

References

• roadmap.sh — Data Structures & Algorithms
• Shortest path problem — Wikipedia
• Dijkstra’s algorithm — Wikipedia
• Bellman–Ford algorithm — Wikipedia
• Floyd–Warshall algorithm — Wikipedia
• A* search algorithm — Wikipedia
• Johnson’s algorithm — Wikipedia
• cp-algorithms — Dijkstra (dense graphs)
• cp-algorithms — Dijkstra on sparse graphs
• cp-algorithms — Bellman-Ford
• cp-algorithms — Floyd-Warshall
• cp-algorithms — 0-1 BFS
• cp-algorithms — Finding a negative cycle in the graph
• Amit Patel — Heuristics for grid maps (Stanford)
• CLRS — Introduction to Algorithms, Chapters 24–25: Shortest Paths
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• VisuAlgo — Single-source shortest paths
• Python Documentation — heapq