Floyd–Warshall all-pairs shortest paths

A small warehouse map answers route-cost questions between many pairs of loading bays throughout a shift. Running a fresh shortest-path search for every pair repeats work; the map is small enough to prepare a complete distance table.

Floyd–Warshall builds that table by allowing intermediate vertices one at a time. The outer loop has a meaning: it decides which stops the routes may use, rather than merely controlling the order of arithmetic.

Preparing routes between every loading bay

Floyd-Warshall increases the allowed intermediate vertex set one vertex at a time. With k outside the other two loops, distance[i][j] can improve through i -> k -> j while preserving the dynamic-programming meaning of each phase.

Allowing one more intermediate stop

With direct costs 0 → 1: 3, 1 → 2: 2, and 0 → 2: 9, allowing stop 1 improves the last route to five. For each pair, compare its existing cost with the cost via the newly allowed stop. Keep the intermediate-stop loop outside both endpoint loops; changing that order loses the staged dependency the update relies on.

using Cost = std::optional<Int>;
std::vector<std::vector<Cost>> distance{
    {0, 3, 9}, {std::nullopt, 0, 2}, {std::nullopt, std::nullopt, 0}
};
for (std::size_t k = 0; k < 3; ++k) {
    for (std::size_t i = 0; i < 3; ++i) {
        for (std::size_t j = 0; j < 3; ++j) {
            if (!distance[i][k] || !distance[k][j]) continue;
            Int candidate = *distance[i][k] + *distance[k][j];
            if (!distance[i][j] || candidate < *distance[i][j]) {
                distance[i][j] = candidate;
            }
        }
    }
}
std::cout << *distance[0][2] << '\n'; // 5, via vertex 1.

Knowing when the full matrix is worthwhile

Initialize the diagonal to zero and retain the cheapest parallel edge. A negative self-loop must still override zero, because it witnesses a negative cycle. Any negative diagonal after relaxation indicates an unbounded cycle anywhere in the graph, even in a component unreachable from some chosen source. This differs from single-source Bellman-Ford's error scope. The matrix requires O(V²) storage and O(V³) time. Using i or j as the outer phase generally loses the recurrence's invariant.

The matrix updates cost O(V³) time and require O(V²) storage; reading the input edges is additional work. A repeated single-source baseline can cost more on dense graphs, but a sparse graph may suit repeated Dijkstra when weights are nonnegative. Any negative cycle is relevant to an all-pairs request.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

The warehouse gets cheap later lookups by accepting the cost of preparing and storing every pair.