Edge Necessity
You have a graph. You know all shortest distances. Now someone asks: which edges actually matter? Which ones sit on a shortest path? Which ones could vanish without changing any distance?
This is edge forensics. You're not finding paths. You're interrogating the graph's skeleton.
The Problem: ABC051-D Candidates of No Shortest Paths
Given a weighted undirected graph with \(N\) nodes (\(N \leq 100\)) and \(M\) edges, count the number of edges that do not lie on any shortest path between any pair of vertices.
Step 1: Compute All-Pairs Shortest Paths
\(N \leq 100\). Floyd-Warshall is perfect.
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
After this, dist[i][j] is the shortest distance from \(i\) to \(j\).
Step 2: Classify Each Edge
For edge \((u, v)\) with weight \(w\), three cases:
Case 1: \(\text{dist}[u][v] < w\). A shorter path exists. This edge is never on any shortest path. It's dead weight.
Case 2: \(\text{dist}[u][v] = w\) and no intermediate vertex achieves the same distance. This edge is the only way to achieve the shortest path between \(u\) and \(v\). It's essential.
Case 3: \(\text{dist}[u][v] = w\) and some vertex \(k\) satisfies \(\text{dist}[u][k] + \text{dist}[k][v] = w\). The edge ties with a multi-hop path. It's on some shortest paths but is redundant.
Edges in Cases 1 and 3 are "not candidates for shortest paths." Count them.
int ans = 0;
for (auto& [u, v, w] : edges) {
if (dist[u][v] < w) { ans++; continue; }
bool redundant = false;
for (int k = 0; k < N; k++) {
if (k == u || k == v) continue;
if (dist[u][k] + dist[k][v] == w) {
redundant = true;
break;
}
}
if (redundant) ans++;
}
Key insight. An edge \((u, v, w)\) is on a shortest path only if \(\text{dist}[u][v] = w\) and no shorter-hop route matches. The second condition is what separates necessary from redundant.
Trace: 5-Node Example
Graph with 5 nodes (0-4) and 7 edges:
| Edge | u | v | w |
|---|---|---|---|
| e0 | 0 | 1 | 2 |
| e1 | 0 | 2 | 4 |
| e2 | 1 | 2 | 1 |
| e3 | 1 | 3 | 5 |
| e4 | 2 | 3 | 2 |
| e5 | 2 | 4 | 3 |
| e6 | 3 | 4 | 1 |
Floyd-Warshall distance matrix:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 2 | 3 | 5 | 6 |
| 1 | 2 | 0 | 1 | 3 | 4 |
| 2 | 3 | 1 | 0 | 2 | 3 |
| 3 | 5 | 3 | 2 | 0 | 1 |
| 4 | 6 | 4 | 3 | 1 | 0 |
Edge classification:
| Edge | w | dist[u][v] | Check | Verdict |
|---|---|---|---|---|
| e0: (0,1) | 2 | 2 | No k gives dist[0][k]+dist[k][1]=2 | Necessary |
| e1: (0,2) | 4 | 3 | dist < w | Dead |
| e2: (1,2) | 1 | 1 | No k gives dist[1][k]+dist[k][2]=1 | Necessary |
| e3: (1,3) | 5 | 3 | dist < w | Dead |
| e4: (2,3) | 2 | 2 | No k gives dist[2][k]+dist[k][3]=2 | Necessary |
| e5: (2,4) | 3 | 3 | k=3: dist[2][3]+dist[3][4]=2+1=3 | Redundant |
| e6: (3,4) | 1 | 1 | No k gives dist[3][k]+dist[k][4]=1 | Necessary |
Answer: 3 edges are not on any shortest path (e1, e3, e5).
Gotcha. Edge e5 has \(w = \text{dist}[2][4] = 3\), so it is a shortest path. But the route \(2 \to 3 \to 4\) also has length 3. The edge is redundant, not dead. The distinction matters.
Variant: ABC243-E Edge Deletion
Same setup, different question. Given a weighted undirected graph, find the maximum number of edges you can delete while preserving all pairwise shortest distances.
The logic is almost identical, with one subtle difference.
An edge \((u, v, w)\) is deletable if there exists any vertex \(k\) such that \(\text{dist}[u][k] + \text{dist}[k][v] \leq w\).
int deletable = 0;
for (auto& [u, v, w] : edges) {
bool can_delete = false;
for (int k = 0; 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";
Gotcha. Notice the \(\leq\) instead of \(=\). In ABC051-D we check \(= w\) to detect redundancy. Here we check \(\leq w\) because even a strictly shorter alternate path makes the edge deletable. An edge with \(\text{dist}[u][v] < w\) is trivially deletable (it was never useful). An edge with \(\text{dist}[u][v] = w\) but an alternate route matching it is also deletable.
Why Floyd-Warshall?
Both problems have \(N \leq 300\). Floyd-Warshall runs in \(O(N^3)\) and gives all-pairs distances in one pass. Dijkstra from every node would work too (\(O(N \cdot M \log N)\)), but Floyd is simpler here.
The edge classification loop is \(O(M \cdot N)\). Total: \(O(N^3 + MN)\).
The Edge Forensics Framework
For any edge \((u, v, w)\) in a graph where all shortest distances are known:
| Condition | Meaning |
|---|---|
| \(\text{dist}[u][v] < w\) | Edge is never on any shortest path |
| \(\text{dist}[u][v] = w\), no bypass exists | Edge is essential for some shortest path |
| \(\text{dist}[u][v] = w\), bypass via \(k\) exists | Edge is redundant (on some shortest paths, but removable) |
This framework applies to any problem that asks "which edges matter?"
Related: Structural Edge Necessity
Two classic problems ask about edge necessity from a connectivity perspective, not shortest paths:
- Bridges (CSES Necessary Roads): edges whose removal disconnects the graph. Found by Tarjan's DFS in \(O(V + E)\).
- Articulation Points (CSES Necessary Cities): vertices whose removal disconnects the graph. Same DFS approach.
These are covered in Chapter 14 (SCC and 2-SAT). The technique is different (DFS low-link values, not Floyd-Warshall), but the question is the same: which parts of the graph are structurally irreplaceable?
LC 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
Floyd-Warshall, then for each city count how many other cities are reachable within distance threshold. Return the city with the smallest count (break ties by largest index).
This is a direct application of all-pairs shortest paths. No edge forensics needed, but it reinforces the Floyd-Warshall pattern.
int best_city = -1, best_count = N + 1;
for (int i = 0; i < N; i++) {
int count = 0;
for (int j = 0; j < N; j++) {
if (i != j && dist[i][j] <= threshold) count++;
}
if (count <= best_count) {
best_count = count;
best_city = i;
}
}
Full Solution: ABC243-E
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N, M;
cin >> N >> M;
vector<vector<ll>> dist(N, vector<ll>(N, 1e18));
for (int i = 0; i < N; i++) dist[i][i] = 0;
vector<array<int,3>> edges(M);
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
u--; v--;
edges[i] = {u, v, w};
dist[u][v] = min(dist[u][v], (ll)w);
dist[v][u] = min(dist[v][u], (ll)w);
}
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
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 = 0; 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";
return 0;
}
Exercises
-
Can an edge with \(\text{dist}[u][v] = w\) be on every shortest path from \(u\) to \(v\)? When?
-
If the graph is a tree, how many edges are "candidates for no shortest path"? Why?
-
In ABC243-E, what happens if you use \(<\) instead of \(\leq\) in the deletion check? Give a counterexample.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC051-D -- Candidates of No Shortest Paths | atcoder.jp/contests/abc051/tasks/abc051_d | Medium |
| ABC243-E -- Edge Deletion | atcoder.jp/contests/abc243/tasks/abc243_e | Medium |
| LC 1334 -- Find the City | leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance | Medium |