the single-source shortest-path problem
Picture a road map where every road has a cost — a distance, a toll, a travel time. You stand at one particular city, call it the source, and you want the cheapest possible route from it to every other city. Not just one destination: all of them at once. That is the single-source shortest-path problem. The answer is a number for each city (the least total cost to reach it) and, if you want, the route that achieves it.
Precisely: you are given a weighted graph, where each edge from u to v carries a weight w(u,v), and a source vertex s. For every vertex v, define dist(v) as the smallest possible sum of edge weights over all paths from s to v (and infinity if v is unreachable). The output is dist(v) for all v. A path's cost is just the sum of its edge weights, so 'shortest' means least total weight, which need not be fewest edges — a three-edge detour of weight 1 each beats a single edge of weight 10. Every correct algorithm for this problem works by repeatedly improving tentative distance estimates through a single operation called edge relaxation, until the estimates equal the true distances.
Which algorithm you use depends on the weights. If all weights are non-negative, Dijkstra's algorithm is fastest. If some weights are negative (but there is no negative cycle), Bellman-Ford works. If the graph is a DAG, relaxing edges in topological order is fastest of all. The problem is everywhere — GPS routing, network packet routing, dependency-cost analysis — and the catch worth remembering is that 'shortest' is meaningless if a negative-weight cycle is reachable, because you could loop it forever and drive the cost to minus infinity.
Vertices s, a, b, t with edges s->a (4), s->b (1), b->a (2), a->t (3), b->t (7). The cheapest way to a is not the direct edge of weight 4, but s->b->a costing 1+2 = 3. Then dist(t) = min(3+3 via a, 1+7 direct b->t) = 6, taking s->b->a->t.
Shortest means least total weight, not fewest edges: a longer detour with small weights can beat one heavy direct edge.
If a negative-weight cycle is reachable from the source, shortest distances to vertices on or beyond it are undefined (minus infinity), so the problem only makes sense once you rule that out.