= Shortest path problem
{title2=$\min_{p:s\leadsto t}\sum_{e\in p}w_e$}
The <shortest path problem> asks for a <graph path> from a source <vertex> $s$ to a destination <vertex> $t$ minimizing its total <edge> weight. Here $w_e$ is the cost of traversing <edge> $e$, and costs add along the <graph path>. If no route exists, its shortest-path distance is $\infty$. With nonnegative <edge> weights, deleting <cycles in a graph> from a <walk> never increases its cost, so repetitions cannot improve the optimum.
Consider the <undirected graph> with <vertex set> $V=\{A,B,C,D\}$ and the six <edge> weights
$$
w_{AB}=4,\quad w_{AC}=1,\quad w_{CB}=2,\quad w_{BD}=1,\quad w_{CD}=5,\quad w_{AD}=10.
$$
Each <edge> can be traversed in either direction at the same cost. The direct <graph path> $A,D$ costs $10$; $A,B,D$ costs $4+1=5$; $A,C,D$ costs $1+5=6$. The cheapest <graph path> is $A,C,B,D$, costing $1+2+1=4$. The remaining <graph path> $A,B,C,D$ costs $11$, exhausting the possibilities without repeated <vertices>.
\Image[/shortest-path-weights.png]
{title=The <shortest path problem>: three highlighted <edges> cost less than the direct connection}
Thus fewest <edges> and least total cost are different objectives. <Breadth-first search> minimizes the number of <edges>, which suffices when every <edge> has the same positive cost. Unequal nonnegative costs call for the <Dijkstra algorithm>. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a <weighted graph> separates the network's connections from what a particular journey costs.
Back to article page
