Shortest path problem (${\min }_{p:s⇝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 weightsEach 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.

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.