the all-pairs shortest-path problem
Single-source asks for the cheapest route from one city to everywhere. All-pairs asks the fuller question: the cheapest route between every pair of cities. Think of building the complete mileage table you sometimes see on the back of a road atlas — a grid where the entry in row i, column j is the shortest distance from city i to city j. All-pairs shortest paths is the problem of filling in that whole table.
Formally, given a weighted graph on V vertices, compute dist(i, j) for every ordered pair (i, j): the least total edge weight of any path from i to j. The output is a V-by-V matrix. One obvious approach is to run a single-source algorithm once from each vertex as the source — V separate runs. With non-negative weights that means V runs of Dijkstra, costing about O(V * (E + V log V)). With negative weights you would need V runs of Bellman-Ford, a heavy O(V^2 * E). The dedicated all-pairs algorithms do better than naive repetition: Floyd-Warshall fills the matrix directly in O(V^3) with beautifully simple code, and Johnson's algorithm reweights the graph once so it can then run fast Dijkstra V times even with negative edges.
All-pairs distances power anything that needs to compare many routes at once: precomputed lookup tables for repeated queries, network-wide latency maps, computing a graph's diameter, and clustering by shortest-path distance. The honest tradeoff is cost. An output of V^2 distances means you can never beat O(V^2) just to write the answer, and the practical methods are O(V^3) territory, so all-pairs is feasible for graphs of hundreds or a few thousand vertices, not millions. For a single route between two specific cities, do NOT solve all-pairs — run one single-source query instead.
For a 4-city graph, the answer is a 4x4 table where row i, column j is dist(i, j); the diagonal is 0 (a city to itself). To get the table on a graph with only non-negative weights, run Dijkstra four times, once per source. On a graph with some negative edges, Floyd-Warshall or Johnson fills the same table while handling the negatives correctly.
All-pairs produces a full V-by-V distance table; you cannot output it faster than O(V^2), and the usual methods cost O(V^3).
Do not run an all-pairs algorithm to answer a single source-to-target query — it is hugely wasteful. All-pairs pays off only when you will issue many distance queries across the whole graph.