the least-cost path

Suppose you want to drive from your town to a friend's town, and every road has a toll. The least-cost path is the route whose tolls add up to the smallest total — not necessarily the one with the fewest towns along the way, and not necessarily the most direct-looking on the map. In a network the 'tolls' are link costs, and finding this cheapest route is the central job of routing.

Precisely: given a weighted graph and a source node, the least-cost path to a destination is a sequence of links from source to destination whose summed cost is minimum over all possible such sequences. If every link has cost 1, this collapses to the fewest-hops path (the literal shortest path by hop count). With unequal costs, the cheapest path can wind through more routers than a pricier direct one. A useful fact algorithms exploit: any sub-path of a least-cost path is itself a least-cost path between its endpoints — this 'optimal substructure' is what lets Dijkstra and Bellman-Ford build answers piece by piece.

This matters because the entire point of a routing algorithm is to compute least-cost paths from each router to every destination, and the forwarding table is essentially the first hop of each of those paths. Get the path computation right and packets flow efficiently; get it wrong and traffic takes long detours or, worse, loops.

An honest caveat: 'least cost' is only as meaningful as the costs you feed in. If costs do not reflect real conditions (say, they ignore current congestion), the least-cost path on paper may not be the fastest in practice. Also, most intra-domain protocols compute paths from static, configured costs, not live traffic — so they optimize a model of the network, not its instantaneous reality.