All-Pairs Applications

Floyd-Warshall computes distances. But the real payoff comes after the algorithm finishes. With all \(V^2\) pairwise distances in hand, you can answer structural questions about the graph: which edges are essential, which are redundant, and what's the minimal graph that preserves all distances. These problems look diverse but share one idea — every edge is either the unique shortest connection between its endpoints or replaceable by a detour.

The Core Question: Is This Edge Necessary?

Graph diameter: the longest shortest path between any two nodes

Transitive closure adds edges for all reachable pairs

Given edge \((u, v, w)\) and the all-pairs distance matrix dist[][], three cases:

Case	Condition	Meaning
Not on any SP	`dist[u][v] < w`	A shorter route exists. Edge is useless.
On a SP but redundant	`dist[u][v] == w` and \(\exists k\): `dist[u][k] + dist[k][v] == w`	Alternative shortest path through \(k\). Deletable.
Necessary	`dist[u][v] == w` and \(\nexists k\): alternative	Unique shortest connection. Must keep.

Key insight. An edge is necessary iff it's on a shortest path AND no alternative shortest path exists through any intermediate node. This single check drives every problem in this lesson.

Worked Example

Graph with 3 nodes:

1 --2-- 2 --3-- 3
 \             /
  \-----5----/

Edges: (1,2,2), (2,3,3), (1,3,5).

After Floyd-Warshall:

	1	2	3
1	0	2	5
2	2	0	3
3	5	3	0

Check each edge:

Edge	dist[u][v] vs w	Intermediate check	Verdict
(1,2,2)	2 == 2	k=3: 5+3=8 > 2. No alternative.	Necessary
(2,3,3)	3 == 3	k=1: 2+5=7 > 3. No alternative.	Necessary
(1,3,5)	5 == 5	k=2: 2+3=5 == 5. Alternative exists!	Redundant

Edge (1,3,5) is deletable. The path \(1 \to 2 \to 3\) already achieves distance 5.

AtCoder abc051_d — Candidates of No Shortest Paths

Problem: Undirected weighted graph, \(N \leq 300\). Count edges that are NOT on any shortest path between any pair.

An edge \((u, v, w)\) lies on some shortest path if and only if dist[u][v] == w. If dist[u][v] < w, the edge is strictly suboptimal — no pair of nodes would ever use it.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    const long long INF = 1e18;
    vector<vector<long long>> dist(n + 1,
        vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    struct Edge { int u, v; long long w; };
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        dist[edges[i].u][edges[i].v] =
            min(dist[edges[i].u][edges[i].v], edges[i].w);
        dist[edges[i].v][edges[i].u] =
            min(dist[edges[i].v][edges[i].u], edges[i].w);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j],
                                     dist[i][k] + dist[k][j]);

    int count = 0;
    for (auto [u, v, w] : edges)
        if (dist[u][v] < w)
            count++;
    cout << count << "\n";
}

The check is just dist[u][v] < w. No intermediate-node scan needed. If the shortest distance between the endpoints is strictly less than the edge weight, the edge is on zero shortest paths.

Gotcha. This problem asks "not on ANY shortest path" — a stricter condition than "deletable." An edge can be on a shortest path yet still be deletable (if an alternative shortest path exists). Here we only count edges that no shortest path uses at all.

AtCoder abc243_e — Edge Deletion

Problem: Undirected weighted graph, \(N \leq 300\) nodes. Find the maximum number of edges you can delete while preserving all-pairs shortest distances. The graph must stay connected.

Edge \((u, v, w)\) is deletable if some intermediate \(k \neq u, v\) gives dist[u][k] + dist[k][v] <= w.

Why \(\leq\) and not just \(<\)? Two sub-cases: - dist[u][k] + dist[k][v] < w: The edge isn't even on a shortest path. Obviously deletable. - dist[u][k] + dist[k][v] == w: The edge is on a shortest path, but an equally short detour exists. Still deletable — the detour preserves the distance.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    const long long INF = 1e18;
    vector<vector<long long>> dist(n + 1,
        vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    struct Edge { int u, v; long long w; };
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        dist[edges[i].u][edges[i].v] =
            min(dist[edges[i].u][edges[i].v], edges[i].w);
        dist[edges[i].v][edges[i].u] =
            min(dist[edges[i].v][edges[i].u], edges[i].w);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j],
                                     dist[i][k] + dist[k][j]);

    int deletable = 0;
    for (auto [u, v, w] : edges) {
        bool can_delete = false;
        for (int k = 1; k <= n; k++) {
            if (k == u || k == v) continue;
            if (dist[u][k] + dist[k][v] <= w) {
                can_delete = true;
                break;
            }
        }
        if (can_delete) deletable++;
    }
    cout << deletable << "\n";
}

Key insight. Connectivity is preserved automatically. If you only delete edges that have alternative shortest paths, the alternative paths themselves guarantee connectivity between the endpoints.

AtCoder arc083_b — Graph Reconstruction

Problem: Given a distance matrix \(A[i][j]\), determine if a valid undirected weighted graph produces exactly this matrix. If yes, output the graph with minimum edges.

Step 1: Validate. The matrix must satisfy: - \(A[i][i] = 0\) for all \(i\) - \(A[i][j] = A[j][i]\) (symmetry) - \(A[i][j] \leq A[i][k] + A[k][j]\) for all \(i, j, k\) (triangle inequality)

If any condition fails, no valid graph exists.

Step 2: Reconstruct. Edge \((i, j)\) with weight \(A[i][j]\) is needed iff no intermediate \(k\) satisfies \(A[i][k] + A[k][j] = A[i][j]\). If a detour matches the distance, the direct edge is redundant.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<long long>> A(n + 1, vector<long long>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> A[i][j];

    // Validate
    for (int i = 1; i <= n; i++) {
        if (A[i][i] != 0) { cout << -1; return 0; }
        for (int j = 1; j <= n; j++) {
            if (A[i][j] != A[j][i]) { cout << -1; return 0; }
            for (int k = 1; k <= n; k++)
                if (A[i][j] > A[i][k] + A[k][j]) {
                    cout << -1;
                    return 0;
                }
        }
    }

    // Find necessary edges
    vector<tuple<int,int,long long>> result;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            bool needed = true;
            for (int k = 1; k <= n; k++) {
                if (k == i || k == j) continue;
                if (A[i][k] + A[k][j] == A[i][j]) {
                    needed = false;
                    break;
                }
            }
            if (needed)
                result.push_back({i, j, A[i][j]});
        }
    }

    cout << result.size() << "\n";
    for (auto [u, v, w] : result)
        cout << u << " " << v << " " << w << "\n";
}

Key insight. Reconstruction is the inverse of Floyd-Warshall. Floyd discovers shortcuts through intermediates. Reconstruction removes all edges that ARE shortcuts — keeping only the irreducible edges.

The Unifying Pattern

All three problems follow one template:

Run Floyd-Warshall.
For each edge (or potential edge), check intermediates.
Classify.

Problem	Per-edge question	Check
abc051_d	On any shortest path?	`dist[u][v] == w`?
abc243_e	Deletable?	\(\exists k\): `dist[u][k] + dist[k][v] <= w`?
arc083_b	Needed in minimal graph?	\(\nexists k\): `A[i][k] + A[k][j] == A[i][j]`?

The intermediate check is \(O(V)\) per edge. Total post-Floyd work: \(O(VE)\) or \(O(V^3)\), dominated by Floyd itself.

LC 1334 — Find the City

Problem: \(N\) cities, weighted edges, threshold \(T\). For each city, count how many others are within distance \(T\). Return the city with the fewest reachable neighbors (ties: largest index).

Run Floyd. For each city \(i\), count \(|\{j \neq i : \text{dist}[i][j] \leq T\}|\). Return the city with minimum count.

// After Floyd-Warshall:
int best = -1, best_count = n + 1;
for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++)
        if (i != j && dist[i][j] <= threshold)
            cnt++;
    if (cnt <= best_count) {
        best_count = cnt;
        best = i;
    }
}

This is a pure Floyd application — no edge analysis. It tests correct Floyd setup and distance querying.

Full Worked Example: Edge Analysis

Graph with 4 nodes and 5 edges:

1 --1-- 2 --1-- 3
 \      |      /
  3     2     1
   \    |    /
    \-- 4 --/

Edges: (1,2,1), (2,3,1), (1,4,3), (2,4,2), (3,4,1).

After Floyd:

	1	2	3	4
1	0	1	2	3
2	1	0	1	2
3	2	1	0	1
4	3	2	1	0

Edge analysis for abc243_e (deletability):

Edge	w	\(\exists k\): `dist[u][k]+dist[k][v] <= w`?	Deletable?
(1,2,1)	1	k=3: 2+1=3>1. k=4: 3+2=5>1. No.	No
(2,3,1)	1	k=1: 1+2=3>1. k=4: 2+1=3>1. No.	No
(1,4,3)	3	k=2: 1+2=3 <= 3. Yes!	Yes
(2,4,2)	2	k=1: 1+3=4>2. k=3: 1+1=2 <= 2. Yes!	Yes
(3,4,1)	1	k=1: 2+3=5>1. k=2: 1+2=3>1. No.	No

Answer: 2 edges deletable. The remaining 3 edges (1,2), (2,3), (3,4) form a path that preserves all shortest distances.

Exercises

Self-check. In the worked example, verify that removing edges (1,4) and (2,4) doesn't change dist[1][4]. What path achieves distance 3?
Directed graphs. If abc243_e used a directed graph, does the deletability check change? (The intermediate check dist[u][k] + dist[k][v] <= w still works because Floyd computes directed distances.)
Counting shortest paths. Extend Floyd to count the number of distinct shortest paths between each pair. When dist[i][k] + dist[k][j] == dist[i][j], how do the counts combine?
Scale limits. abc243_e has \(N \leq 300\). Floyd costs \(300^3 = 2.7 \times 10^7\). The edge check adds \(O(NM)\). What's the maximum \(N\) where this approach still fits in 2 seconds?

Problems

Problem	Link	Difficulty
AtCoder abc051_d — Candidates of No Shortest Paths	atcoder.jp/contests/abc051/tasks/abc051_d	Medium
AtCoder abc243_e — Edge Deletion	atcoder.jp/contests/abc243/tasks/abc243_e	Medium
AtCoder arc083_b — Graph Reconstruction	atcoder.jp/contests/arc083/tasks/arc083_b	Hard
LC 1334 — Find the City	leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance	Medium