---
title: Shortest Paths
module: Graphs
moduleNumber: 6
lessonNumber: 6
order: 606
summary: |
  Finding the cheapest route through a weighted network is one of the most-used
  algorithms in computing, and a single operation — _relaxation_ — underlies
  every method. We build the primitive, prove the triangle inequality and
  optimal substructure that make it work, then meet Dijkstra's algorithm: the
  greedy solution for non-negative weights, traced vertex by vertex, with the
  cut argument that proves each extraction is final.
topics: [Shortest Paths]
sources:
  - book: CLRS
    ref: "Ch. 24 — Single-Source Shortest Paths"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms"
  - book: Erickson
    ref: "Ch. 8 — Shortest Paths"
practice:
  - title: 'Network Delay Time'
    slug: network-delay-time
    difficulty: Medium
  - title: 'Path with Maximum Probability'
    slug: path-with-maximum-probability
    difficulty: Medium
---


Every navigation app, every network router, every game pathfinder is solving the
same problem: given a weighted graph, find the cheapest route from one place to
another. [BFS](/algorithms/graphs/representations-and-traversal) already solved
this when every edge counts as one step. Now the edges carry **weights** (distances,
times, costs), and we want to minimize the _total_ weight along a path. This lesson
builds the shortest-path toolkit from a single primitive shared by every algorithm
in it.

## The problem and its primitive

> **Definition (Shortest-path distance).** Given a weighted directed graph $G = (V, E)$ with weight $w(u, v)$ on each
> edge, the **weight of a path** $p = \vector{v_0, v_1, \dots, v_k}$ is
> $w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$. The **shortest-path distance**
> $\delta(u, v)$ is the minimum weight over all paths from $u$ to $v$ (or
> $\infty$ if none exists). The **single-source shortest paths** (SSSP) problem
> asks for $\delta(s, v)$ from a fixed source $s$ to _every_ vertex $v$.

Every algorithm maintains two arrays. For each vertex $v$, an estimate $v.d$ is
an _upper bound_ on $\delta(s, v)$, always $\ge$ the true distance, shrinking
toward it. A predecessor $v.\pi$ records the previous vertex on the best path
found so far, forming a **shortest-path tree**. We initialize $s.d = 0$ and
$v.d = \infty$ for every other vertex.

The one operation that updates these estimates is **relaxation**: testing
whether going _through_ $u$ improves our route to $v$.

```algorithm
caption: $\textsc{Relax}(u, v, w)$ — try the edge $(u,v)$ as a shortcut to $v$
number: 1
if $u.d + w(u, v) < v.d$ then
  $v.d \gets u.d + w(u, v)$ // cheaper route to v via u
  $v.\pi \gets u$
```

Relaxation never produces an estimate below the true distance, and it can only
ever _lower_ an estimate. Every shortest-path algorithm below is a different
discipline for _deciding which edges to relax, and in what order_. Two facts
make relaxation work: the **triangle inequality**
$\delta(s, v) \le \delta(s, u) + w(u, v)$, and **optimal substructure**: any
subpath of a shortest path is itself a shortest path.[^clrs-relax] The latter is what makes
greedy and dynamic-programming approaches both viable.

One relaxation step looks like this. Before, $v$'s best-known route costs
$9$; we test the edge $(u, v)$ of weight $3$ against $u$'s settled estimate
$u.d = 5$. Since $5 + 3 = 8 < 9$, the edge is a shortcut: $v.d$ drops to $8$ and
$v.\pi$ is rewired to point back through $u$.

$$
% caption: One $\textsc{Relax}(u, v, w)$ step. The edge $u \to v$ beats $v$'s current
%          estimate ($5 + 3 < 9$), so $v.d$ falls to $8$ and its predecessor is rewired to
%          $u$.
\begin{tikzpicture}[>=Stealth, font=\small,
  V/.style={circle, draw, minimum size=11mm, font=\small},
  old/.style={font=\scriptsize},
  rel/.style={->, line width=1.2pt, draw=red!75!black}]
  \definecolor{acc}{HTML}{2348F2}
  % before
  \node[font=\footnotesize] at (1.4,1.7) {before};
  \node[V] (u1) at (0,0) {$5$};
  \node[V] (v1) at (2.8,0) {$9$};
  \node[old] at (0,-1.0) {u.d = 5};
  \node[old] at (2.8,-1.0) {v.d = 9};
  \draw[->] (u1) -- node[font=\scriptsize, above]{$3$} (v1);
  % after
  \begin{scope}[xshift=58mm]
    \node[font=\footnotesize] at (1.4,1.7) {after relax};
    \node[V] (u2) at (0,0) {$5$};
    \node[V, draw=acc, very thick, fill=acc!15] (v2) at (2.8,0) {$8$};
    \node[old] at (0,-1.0) {u.d = 5};
    \node[old, acc] at (2.8,-1.0) {v.d = 8};
    \draw[rel] (u2) -- node[font=\scriptsize, above]{$3$} (v2);
    \node[font=\scriptsize, acc] at (1.4,-1.7) {v.pred = u};
  \end{scope}
\end{tikzpicture}
$$

We will trace the algorithms on this small weighted digraph. The
**negative edge** $a \to b$ of weight $-2$ is harmless here (there is no
negative _cycle_), but edges like it are what break Dijkstra
and force a dynamic program.

$$
% caption: A small weighted digraph with one negative edge $a$ to $b$ of weight $-2$, used
%          to trace the algorithms.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=8mm, font=\small},
  wt/.style={font=\scriptsize, fill=white, inner sep=1.5pt},
  >={Stealth[round]}, node distance=22mm]
  \node[vtx] (s) {$s$};
  \node[vtx] (a) [above right=8mm and 22mm of s] {$a$};
  \node[vtx] (b) [below right=8mm and 22mm of s] {$b$};
  \node[vtx] (c) [right=22mm of a] {$c$};
  \node[vtx] (t) [below right=8mm and 22mm of c] {$t$};
  \draw[->] (s) -- node[wt,above left]{$10$} (a);
  \draw[->] (s) -- node[wt,below left]{$5$} (b);
  \draw[->] (a) -- node[wt,left]{-2} (b);
  \draw[->] (a) -- node[wt,above]{$1$} (c);
  \draw[->] (b) -- node[wt,below,pos=0.4]{$9$} (c);
  \draw[->] (c) -- node[wt,above right]{$4$} (t);
  \draw[->] (b) -- node[wt,below]{$2$} (t);
\end{tikzpicture}
$$

## Dijkstra's algorithm

When _all edge weights are non-negative_, we can be greedy. $\textsc{Dijkstra}$'s
algorithm grows a set $S$ of vertices whose shortest distances are _finalized_.
At each step it picks the non-finalized vertex $u$ with the smallest estimate
$u.d$, finalizes it, and relaxes its outgoing edges. A
[min-priority queue](/algorithms/sorting/heaps-and-heapsort) keyed
by $d$ supplies the next vertex.

```algorithm
caption: $\textsc{Dijkstra}(G, w, s)$ — SSSP for non-negative weights
number: 2
foreach vertex $v \in V$ do
  $v.d \gets \infty$
  $v.\pi \gets \text{nil}$
$s.d \gets 0$
$S \gets \emptyset$
$Q \gets V$ // min-PQ keyed by d
while $Q \neq \emptyset$ do
  $u \gets$ $\textsc{Extract-Min}(Q)$ // closest unfinalized
  $S \gets S \cup \set{u}$ // u.d now final
  foreach $v$ adjacent to $u$ do
    call $\textsc{Relax}(u, v, w)$ // Decrease-Key updates Q
return $d$ and $\pi$
```

Correctness rests on a **cut argument** — the same $S$ versus $V \setminus S$
split that powered the exchange proofs for
[minimum spanning trees](/algorithms/graphs/minimum-spanning-trees). The
correctness claim is a loop invariant, and unwinding it across the whole run
gives the theorem that justifies the greedy commitment.

> **Invariant (Dijkstra).** At the start of each iteration of the `while` loop,
> every _finalized_ vertex already holds its true distance:
> $$\forall x \in S:\quad x.d = \delta(s, x).$$

> **Theorem (Extraction is final).** With non-negative edge weights, at the
> moment $\textsc{Dijkstra}$ extracts a vertex $u$ from the queue,
> $u.d = \delta(s, u)$. Since relaxation never raises an estimate and never
> drives one below the true distance, $u.d$ never changes again: extraction
> _is_ finalization.

> **Proof.** The first extraction is $s$ itself, with $s.d = 0 = \delta(s, s)$.
> Suppose for contradiction that extracting $u$ were the **first** extraction to
> violate the theorem. Then either $u.d$ is too _low_ or too _high_.
>
> - _Too low_ ($u.d < \delta(s, u)$) is impossible, because relaxation never drops
>   an estimate below the true distance — every value of $u.d$ is the cost of some
>   real $s \rightsquigarrow u$ walk.
> - _Too high_ ($u.d > \delta(s, u)$): let $p$ be a genuine shortest path from
>   $s$ to $u$. Walk $p$ from $s$ (inside $S$) toward $u$ (outside it), and let
>   $(x, y)$ be the **first edge that crosses the cut** — so $x \in S$,
>   $y \notin S$. By the invariant $x.d = \delta(s, x)$, and $(x, y)$ was relaxed
>   when $x$ was finalized, so
>   $y.d = \delta(s, x) + w(x, y) = \delta(s, y)$. Now $y$ sits on a shortest path
>   to $u$, and **because every weight is $\ge 0$**, the rest of $p$ only adds
>   cost: $\delta(s, y) \le \delta(s, u) \le u.d$. Hence $y.d \le u.d$, so
>   $\textsc{Extract-Min}$ would have returned $y$, not $u$ — contradiction. $\qed$

The non-negativity is doing all the work in that last inequality: it guarantees
extending a path never _decreases_ its cost, so the closest frontier vertex can
be safely frozen. A single negative edge breaks $\delta(s, y) \le \delta(s, u)$,
so the greedy commitment becomes unsound; the failure is exhibited concretely
below.

### A complete run

Here is a full run: every $\textsc{Extract-Min}$, every successful
relaxation, and the queue contents after each step. The graph has vertices
$s, a, b, c, t$ and edges $s \to a$ ($4$), $s \to b$ ($1$), $b \to a$ ($2$),
$b \to c$ ($5$), $a \to c$ ($1$), $a \to t$ ($6$), $c \to t$ ($3$). Read a
table entry $4_s$ as "$v.d = 4$ with $v.\pi = s$"; **bold** marks a finalized
estimate, which never moves again.

| Step | Extracted (key) | $s$ | $a$ | $b$ | $c$ | $t$ | Queue after (vertex: key) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| init | — | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $s{:}0,\; a{:}\infty,\; b{:}\infty,\; c{:}\infty,\; t{:}\infty$ |
| 1 | $s$ $(0)$ | $\mathbf{0}$ | $4_s$ | $1_s$ | $\infty$ | $\infty$ | $b{:}1,\; a{:}4,\; c{:}\infty,\; t{:}\infty$ |
| 2 | $b$ $(1)$ | $\mathbf{0}$ | $3_b$ | $\mathbf{1}_s$ | $6_b$ | $\infty$ | $a{:}3,\; c{:}6,\; t{:}\infty$ |
| 3 | $a$ $(3)$ | $\mathbf{0}$ | $\mathbf{3}_b$ | $\mathbf{1}_s$ | $4_a$ | $9_a$ | $c{:}4,\; t{:}9$ |
| 4 | $c$ $(4)$ | $\mathbf{0}$ | $\mathbf{3}_b$ | $\mathbf{1}_s$ | $\mathbf{4}_a$ | $7_c$ | $t{:}7$ |
| 5 | $t$ $(7)$ | $\mathbf{0}$ | $\mathbf{3}_b$ | $\mathbf{1}_s$ | $\mathbf{4}_a$ | $\mathbf{7}_c$ | — |

Two steps in the trace show the mechanism. In step 2, extracting $b$
triggers a $\textsc{Decrease-Key}$ on $a$: the tentative $4_s$ (the direct
edge) is beaten by $1 + 2 = 3$ through $b$, so $a$'s queue key drops and its
predecessor is rewired. In step 3, the same thing happens to $c$: $6_b$ falls
to $4_a$. Both improvements arrive _before_ the affected vertex is extracted; the
theorem guarantees this ordering can never fail with non-negative weights. The
final predecessor array spells out the shortest-path tree:
$t \gets c \gets a \gets b \gets s$.

$$
% caption: The run as a state sequence, one panel per $\textsc{Extract-Min}$. Shaded
%          vertices are finalized; the label beside each vertex is its current key
%          (black once finalized, blue while still in the queue), and the blue edges
%          are the ones relaxed in that step.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \tikzset{
    V/.style={circle, draw, minimum size=6.5mm, font=\small, inner sep=0.5pt},
    F/.style={V, fill=acc!15, draw=acc, thick},
    wt/.style={font=\scriptsize, inner sep=1pt},
    dl/.style={font=\scriptsize},
    ky/.style={font=\scriptsize, acc},
    rx/.style={->, draw=acc, thick}}
  % panel 1: extract s, relax (s,a) and (s,b)
  \begin{scope}
    \node[font=\footnotesize] at (2.7,2.15) {1. settle s};
    \node[F] (s) at (0,0) {$s$};
    \node[V] (a) at (1.8,1.0) {$a$};
    \node[V] (b) at (1.8,-1.0) {$b$};
    \node[V] (c) at (3.8,0) {$c$};
    \node[V] (t) at (5.4,0) {$t$};
    \draw[rx] (s) -- node[wt, above left]{$4$} (a);
    \draw[rx] (s) -- node[wt, below left]{$1$} (b);
    \draw[->] (b) -- node[wt, left]{$2$} (a);
    \draw[->] (b) -- node[wt, below]{$5$} (c);
    \draw[->] (a) -- node[wt, above]{$1$} (c);
    \draw[->] (a) to[bend left=28] node[wt, above]{$6$} (t);
    \draw[->] (c) -- node[wt, below]{$3$} (t);
    \node[dl] at (0,-0.65) {0};
    \node[ky] at (1.0,1.42) {4};
    \node[ky] at (1.8,-1.6) {1};
    \node[ky] at (3.8,0.62) {inf};
    \node[ky] at (5.4,-0.62) {inf};
  \end{scope}
  % panel 2: extract b, relax (b,a) and (b,c)
  \begin{scope}[xshift=74mm]
    \node[font=\footnotesize] at (2.7,2.15) {2. settle b};
    \node[F] (s) at (0,0) {$s$};
    \node[V] (a) at (1.8,1.0) {$a$};
    \node[F] (b) at (1.8,-1.0) {$b$};
    \node[V] (c) at (3.8,0) {$c$};
    \node[V] (t) at (5.4,0) {$t$};
    \draw[->] (s) -- node[wt, above left]{$4$} (a);
    \draw[->] (s) -- node[wt, below left]{$1$} (b);
    \draw[rx] (b) -- node[wt, left]{$2$} (a);
    \draw[rx] (b) -- node[wt, below]{$5$} (c);
    \draw[->] (a) -- node[wt, above]{$1$} (c);
    \draw[->] (a) to[bend left=28] node[wt, above]{$6$} (t);
    \draw[->] (c) -- node[wt, below]{$3$} (t);
    \node[dl] at (0,-0.65) {0};
    \node[ky] at (1.0,1.42) {3};
    \node[dl] at (1.8,-1.6) {1};
    \node[ky] at (3.8,0.62) {6};
    \node[ky] at (5.4,-0.62) {inf};
  \end{scope}
  % panel 3: extract a, relax (a,c) and (a,t)
  \begin{scope}[yshift=-48mm]
    \node[font=\footnotesize] at (2.7,2.15) {3. settle a};
    \node[F] (s) at (0,0) {$s$};
    \node[F] (a) at (1.8,1.0) {$a$};
    \node[F] (b) at (1.8,-1.0) {$b$};
    \node[V] (c) at (3.8,0) {$c$};
    \node[V] (t) at (5.4,0) {$t$};
    \draw[->] (s) -- node[wt, above left]{$4$} (a);
    \draw[->] (s) -- node[wt, below left]{$1$} (b);
    \draw[->] (b) -- node[wt, left]{$2$} (a);
    \draw[->] (b) -- node[wt, below]{$5$} (c);
    \draw[rx] (a) -- node[wt, above]{$1$} (c);
    \draw[rx] (a) to[bend left=28] node[wt, above]{$6$} (t);
    \draw[->] (c) -- node[wt, below]{$3$} (t);
    \node[dl] at (0,-0.65) {0};
    \node[dl] at (1.0,1.42) {3};
    \node[dl] at (1.8,-1.6) {1};
    \node[ky] at (3.8,0.62) {4};
    \node[ky] at (5.4,-0.62) {9};
  \end{scope}
  % panel 4: extract c, relax (c,t)
  \begin{scope}[xshift=74mm, yshift=-48mm]
    \node[font=\footnotesize] at (2.7,2.15) {4. settle c};
    \node[F] (s) at (0,0) {$s$};
    \node[F] (a) at (1.8,1.0) {$a$};
    \node[F] (b) at (1.8,-1.0) {$b$};
    \node[F] (c) at (3.8,0) {$c$};
    \node[V] (t) at (5.4,0) {$t$};
    \draw[->] (s) -- node[wt, above left]{$4$} (a);
    \draw[->] (s) -- node[wt, below left]{$1$} (b);
    \draw[->] (b) -- node[wt, left]{$2$} (a);
    \draw[->] (b) -- node[wt, below]{$5$} (c);
    \draw[->] (a) -- node[wt, above]{$1$} (c);
    \draw[->] (a) to[bend left=28] node[wt, above]{$6$} (t);
    \draw[rx] (c) -- node[wt, below]{$3$} (t);
    \node[dl] at (0,-0.65) {0};
    \node[dl] at (1.0,1.42) {3};
    \node[dl] at (1.8,-1.6) {1};
    \node[dl] at (3.8,0.62) {4};
    \node[ky] at (5.4,-0.62) {7};
  \end{scope}
\end{tikzpicture}
$$

Vertices finalize in nondecreasing order of distance ($s, b, a, c, t$) —
a direct consequence of the greedy invariant. Notice that
$a$ is finalized at distance $3$ via the two-hop route $s \to b \to a$, _beating_
the direct edge $s \to a$ of weight $4$ — the relaxation through $b$ fired before
$a$ was ever extracted:

$$
% caption: Dijkstra finalizes vertices in nondecreasing distance:
%          $s(0), b(1), a(3), c(4), t(7)$. Vertex $a$ settles at $3$ via $s \to b \to a$,
%          beating the direct edge of weight $4$.
\begin{tikzpicture}[>=Stealth, font=\small,
  V/.style={circle, draw, minimum size=8mm, font=\small},
  wt/.style={font=\scriptsize, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (s) at (0,0) {$s$};
  \node[V] (b) at (1.8,-1.0) {$b$};
  \node[V] (a) at (1.8,1.0) {$a$};
  \node[V] (c) at (3.8,0) {$c$};
  \node[V] (t) at (5.6,0) {$t$};
  \draw[->] (s) -- node[wt, above left]{$4$} (a);
  \draw[->] (s) -- node[wt, below left]{$1$} (b);
  \draw[->] (b) -- node[wt, left]{$2$} (a);
  \draw[->] (b) -- node[wt, below]{$5$} (c);
  \draw[->] (a) -- node[wt, above]{$1$} (c);
  \draw[->] (a) to[bend left=30] node[wt, above]{$6$} (t);
  \draw[->] (c) -- node[wt, below]{$3$} (t);
  \node[font=\footnotesize] at (0.3,-2.3) {\textbf{settled:}};
  \foreach \v/\dd/\x in {s/0/2.0, b/1/2.9, a/3/3.8, c/4/4.7, t/7/5.6}
    \node[draw, fill=acc!12, minimum size=6mm, font=\scriptsize] at (\x,-2.3) {$\v{:}\dd$};
\end{tikzpicture}
$$

**Running time.** Like [Prim](/algorithms/graphs/minimum-spanning-trees), Dijkstra
does exactly $\abs{V}$ $\textsc{Extract-Min}$ operations (each vertex leaves the
queue once) and at most $\abs{E}$ $\textsc{Decrease-Key}$ operations (each edge
is relaxed once, when its tail is extracted, and each successful relaxation is
one key decrease). The total is therefore
$$
V \cdot T_{\textsc{Extract-Min}} + E \cdot T_{\textsc{Decrease-Key}}.
$$
With a binary heap both operations cost $O(\log V)$, giving
$O((V + E)\log V)$, which is $O(E \log V)$ whenever every vertex is reachable,
since then $E \ge V - 1$. A Fibonacci heap makes $\textsc{Decrease-Key}$
amortized $O(1)$, improving the bound to $O(E + V\log V)$. The gap matters most
on dense graphs: with $E = \Theta(V^2)$, the binary heap pays
$\Theta(V^2 \log V)$ while the Fibonacci heap pays $\Theta(V^2)$.

### Why negative edges break it

The theorem leaned on non-negativity exactly once, in the step "the rest of $p$
only adds cost", and one negative edge is enough to break it. Take three vertices:
$s \to a$ with weight $1$, $s \to b$ with weight $2$, and $b \to a$ with weight
$-2$. The true distance to $a$ is $\delta(s, a) = 2 + (-2) = 0$ via $b$. But
Dijkstra extracts $s$, then extracts $a$ (key $1$, the current minimum) and
freezes $a.d = 1$. Only afterward does it extract $b$ and try the edge
$(b, a)$: the relaxation $2 + (-2) = 0 < 1$ would succeed, but $a$ has already
left the queue, and the algorithm never revisits a finalized vertex. The
greedy schedule processed $a$ before the cheap route to it existed.

$$
% caption: A negative edge poisons the greedy choice. Here $\delta(s, a) = 0$ via
%          $s \to b \to a$, but Dijkstra extracts $a$ second with $a.d = 1$ and freezes
%          it; the improving relaxation of $(b, a)$ fires only after $b$ is extracted —
%          too late for a finalized vertex.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \tikzset{V/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0.5pt},
    wt/.style={font=\scriptsize, fill=white, inner sep=1.5pt},
    tag/.style={font=\scriptsize, black}}
  \node[V] (s) at (0,0) {$s$};
  \node[V, draw=red!75!black, thick] (a) at (3.6,1.1) {$a$};
  \node[V] (b) at (3.6,-1.1) {$b$};
  \draw[->] (s) -- node[wt, above left]{1} (a);
  \draw[->] (s) -- node[wt, below left]{2} (b);
  \draw[->, draw=red!75!black, thick] (b) -- node[wt, left]{-2} (a);
  \node[tag] at (0,-0.8) {settled 1st};
  \node[tag, right] at (4.15,1.1) {settled 2nd, d = 1};
  \node[tag, right] at (4.15,-1.1) {settled 3rd, d = 2};
  \node[font=\scriptsize, acc] at (3.6,1.95) {true distance: 0};
  \node[font=\scriptsize, red!75!black, right] at (4.15,0) {relaxed late};
\end{tikzpicture}
$$

A tempting repair, adding a constant to every edge weight until none is
negative, fails because it penalizes paths in proportion to their _hop count_: a
three-edge path gains $3c$ while a one-edge path gains only $c$, so the
reweighted graph can have a different shortest path. Handling negative edges
requires giving up the greedy schedule in favor of dynamic programming.

::impl{algo="dijkstra"}

## How a map app really routes

Dijkstra explores in every direction at once, which is wasteful on a continent-sized road network. Production route planners keep the relaxation primitive but prune the search hard.

**A\* search.** Give the algorithm a _heuristic_ $h(v)$, a lower bound on the remaining distance from $v$ to the target $t$ (straight-line distance on a map). A\* extracts the vertex minimizing $v.d + h(v)$ instead of $v.d$, biasing the frontier toward the goal.[^astar] When $h$ is **admissible** (never overestimates) and **consistent** ($h(u) \le w(u,v) + h(v)$), A\* returns an exact shortest path while touching far fewer vertices than Dijkstra — and with $h \equiv 0$ it _is_ Dijkstra, so the two sit on one spectrum. A\* is really Dijkstra on the reweighted graph $w'(u,v) = w(u,v) - h(u) + h(v)$, and it is consistency that keeps those weights non-negative.

$$
% caption: A* versus Dijkstra on a grid. Dijkstra's frontier (light) expands as a disk
%          around $s$; A*'s (blue) is pulled toward $t$ by the heuristic, settling far
%          fewer cells.
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \fill[black] (0,0) circle (1.5cm);
  \node[circle, draw, fill=white, minimum size=6mm] (s1) at (0,0) {$s$};
  \node[circle, draw, fill=white, minimum size=6mm] (t1) at (2.6,0) {$t$};
  \node[font=\scriptsize] at (0,-1.9) {Dijkstra: disk};
  \begin{scope}[xshift=62mm]
    \fill[acc!18] (0,0) -- (2.6,0.55) -- (2.6,-0.55) -- cycle;
    \node[circle, draw, fill=white, minimum size=6mm] (s2) at (0,0) {$s$};
    \node[circle, draw, fill=white, minimum size=6mm] (t2) at (2.6,0) {$t$};
    \node[font=\scriptsize] at (1.3,-1.9) {A*: wedge toward $t$};
  \end{scope}
\end{tikzpicture}
$$

**Bidirectional search** runs two Dijkstras at once, one forward from $s$ and one backward from $t$, and stops when their frontiers meet; each explores roughly a hemisphere instead of a full ball, halving the exponent of the searched area.

**Contraction hierarchies** go further for the road-network case where the graph is fixed and queried millions of times.[^ch] A one-time preprocessing pass ranks vertices by importance and adds _shortcut_ edges that bypass unimportant ones, so a query only ever climbs the hierarchy from $s$ and $t$ toward their meeting point. After preprocessing, continent-scale point-to-point queries finish in microseconds — the machinery behind the instant routes in a navigation app.

**On the theory side,** Duan, Mao, Mao, Shu, and Yin (2025) gave the first SSSP algorithm to break Dijkstra's sorting bottleneck on directed graphs with real non-negative weights, running in $O(m \log^{2/3} n)$ — evidence that even this settled-seeming problem still has room below $O(m + n\log n)$.[^sorting-barrier]

This continues in [All-Pairs and Negative Weights](/algorithms/graphs/all-pairs-and-negative-weights), where we give up the greedy schedule to handle negative edges (Bellman-Ford as a dynamic program) and compute the distance between _every_ pair of vertices (Floyd-Warshall).

[^clrs-relax]: **CLRS**, Ch. 24 & 25 — Single-Source and All-Pairs Shortest Paths — relaxation, the triangle inequality, and optimal substructure.
[^astar]: **Hart, Nilsson & Raphael** (1968), "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," _IEEE Trans. Systems Science and Cybernetics_ 4(2), 100–107 — the A* algorithm and its admissibility conditions.
[^ch]: **Geisberger, Sanders, Schultes & Delling** (2008), "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks," _Proc. WEA 2008_ — shortcut-based preprocessing for fast road-network queries.
[^sorting-barrier]: **Duan, Mao, Mao, Shu & Yin** (2025), "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths," _Proc. STOC 2025_ — SSSP in $O(m \log^{2/3} n)$, below Dijkstra's sorting bound.