shortest path
The shortest-path problem asks: starting at one vertex, what is the cheapest way to reach another, adding up the weights of the edges you cross? This is the math behind a navigation app routing you the fastest way home, a network choosing the lowest-latency route, or a game character finding the cheapest path across terrain. 'Shortest' means least total weight, which is not always the fewest edges.
If the graph is unweighted (every edge counts as one step), the answer is simply the fewest edges, and breadth-first search already solves it in O(V + E). Once edges carry different weights, you need an algorithm that always considers the cheapest-known frontier first. Dijkstra's algorithm does exactly that: it grows a set of vertices with finalized shortest distances, each time picking the unfinalized vertex with the smallest tentative distance and relaxing its outgoing edges (updating a neighbor if going through this vertex is cheaper).
Dijkstra's algorithm assumes non-negative edge weights — a negative edge can break its greedy reasoning, and for that case you need a different method such as Bellman-Ford. Implemented with a priority queue (a binary heap), Dijkstra runs in about O((V + E) log V), efficient enough for large road networks and the most widely used single-source shortest-path algorithm in practice.
// pq holds {distance, vertex}, smallest first
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue; // stale entry
for (auto [nb, w] : adj[v])
if (dist[v] + w < dist[nb]) {
dist[nb] = dist[v] + w;
pq.push({dist[nb], nb});
}Pop the closest vertex, then improve any neighbor reachable more cheaply through it.
Use BFS for unweighted graphs, Dijkstra for non-negative weights, and Bellman-Ford when negative edge weights are possible.