Skip to content

Graph Reconstruction

Distance matrix to minimum-edge graph reconstruction

Floyd-Warshall takes a graph and produces a distance matrix. What about the reverse? Given a distance matrix, can you recover the graph?

This is the inverse of shortest-path computation. And it turns out the answer is clean, elegant, and deeply connected to the edge forensics from the previous lesson.

The Problem: ARC083-B Restoring Road Network

Given an \(N \times N\) matrix \(A\) where \(A[i][j]\) is the claimed shortest distance between cities \(i\) and \(j\). Determine:

  1. Does a weighted undirected graph exist whose all-pairs shortest distances equal \(A\)?
  2. If yes, what is the minimum total edge weight among all such graphs?

Constraints: \(N \leq 300\), \(A[i][j] \leq 10^9\).

Step 1: Validate the Matrix

A distance matrix must satisfy three properties:

Zero diagonal. \(A[i][i] = 0\) for all \(i\).

Symmetry. \(A[i][j] = A[j][i]\) for all \(i, j\).

Triangle inequality. \(A[i][j] \leq A[i][k] + A[k][j]\) for all \(i, j, k\).

If any of these fail, no valid graph exists. Output \(-1\).

bool valid = true;
for (int i = 0; i < N && valid; i++) {
    if (A[i][i] != 0) valid = false;
    for (int j = 0; j < N && valid; j++) {
        if (A[i][j] != A[j][i]) valid = false;
        for (int k = 0; k < N && valid; k++) {
            if (A[i][j] > A[i][k] + A[k][j]) valid = false;
        }
    }
}
if (!valid) { cout << -1 << "\n"; return 0; }

Gotcha. The triangle inequality check is strict: \(A[i][j] > A[i][k] + A[k][j]\), not \(\geq\). Equality is fine --- it just means there's a multi-hop shortest path.

Step 2: Find the Minimum Graph

Now we know a valid graph exists. Which edges should it contain?

Consider the potential edge \((i, j)\) with weight \(A[i][j]\). This edge is necessary only if no intermediate vertex \(k\) achieves \(A[i][k] + A[k][j] = A[i][j]\).

If some \(k\) achieves it, the shortest path from \(i\) to \(j\) can go through \(k\) without a direct edge. The edge is redundant.

ll total = 0;
for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        bool needed = true;
        for (int k = 0; k < N; k++) {
            if (k == i || k == j) continue;
            if (A[i][k] + A[k][j] == A[i][j]) {
                needed = false;
                break;
            }
        }
        if (needed) total += A[i][j];
    }
}
cout << total << "\n";

Key insight. This is exactly the edge classification from Lesson 2, but in reverse. In Lesson 2, we had a graph and asked which edges were necessary. Here, we have distances and construct only the necessary edges. Same test, opposite direction.

Why This Works

Claim: the graph containing exactly the necessary edges produces distance matrix \(A\).

Proof sketch:

  1. Every necessary edge \((i, j)\) has weight \(A[i][j]\), so \(\text{dist}(i, j) \leq A[i][j]\).

  2. For a redundant pair \((i, j)\), some \(k\) satisfies \(A[i][k] + A[k][j] = A[i][j]\). By induction, the necessary edges already produce \(\text{dist}(i, k) = A[i][k]\) and \(\text{dist}(k, j) = A[k][j]\). So \(\text{dist}(i, j) \leq A[i][j]\).

  3. No distance can be shorter than \(A[i][j]\) because every edge has weight \(\geq A[u][v]\) (we only use weights from the matrix), and the triangle inequality holds.

Therefore \(\text{dist}(i, j) = A[i][j]\) for all pairs.

Trace: 4-Node Distance Matrix

Input matrix \(A\):

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

Validation: triangle inequality holds. For example, \(A[0][3] = 3 \leq A[0][1] + A[1][3] = 1 + 2 = 3\). Check.

Edge necessity check:

Pair (i,j) A[i][j] Bypass via k? Necessary?
(0,1) 1 k=2: 2+1=3 > 1. k=3: 3+2=5 > 1. Yes
(0,2) 2 k=1: 1+1=2 = 2. Bypass found. No
(0,3) 3 k=1: 1+2=3 = 3. Bypass found. No
(1,2) 1 k=0: 1+2=3 > 1. k=3: 2+1=3 > 1. Yes
(1,3) 2 k=2: 1+1=2 = 2. Bypass found. No
(2,3) 1 k=0: 2+3=5 > 1. k=1: 1+2=3 > 1. Yes

Necessary edges: (0,1) w=1, (1,2) w=1, (2,3) w=1.

Total weight: \(1 + 1 + 1 = 3\).

The minimum graph is a path: \(0 - 1 - 2 - 3\).

The Floyd-Warshall Duality

Floyd-Warshall and graph reconstruction are inverse operations:

Operation Input Output
Floyd-Warshall Edge list (graph) Distance matrix
Graph reconstruction Distance matrix Edge list (minimum graph)

The reconstruction uses the exact same triple loop structure as Floyd-Warshall but asks the opposite question. Floyd asks: "can vertex \(k\) improve the path from \(i\) to \(j\)?" Reconstruction asks: "does vertex \(k\) make the direct edge from \(i\) to \(j\) unnecessary?"

Key insight. If you understand Floyd-Warshall, you already understand graph reconstruction. They're the same algorithm reading the same data with opposite intent.

Full Solution Code

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

int main() {
    int N;
    cin >> N;
    vector<vector<ll>> A(N, vector<ll>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> A[i][j];

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

    // Find minimum graph
    ll total = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            bool needed = true;
            for (int k = 0; k < N; k++) {
                if (k == i || k == j) continue;
                if (A[i][k] + A[k][j] == A[i][j]) {
                    needed = false;
                    break;
                }
            }
            if (needed) total += A[i][j];
        }
    }

    cout << total << "\n";
    return 0;
}

Complexity

  • Validation: \(O(N^3)\).
  • Edge necessity: \(O(N^3)\) (for each of \(O(N^2)\) pairs, check \(O(N)\) intermediates).
  • Total: \(O(N^3)\). Same as Floyd-Warshall itself.

For \(N = 300\), that's \(2.7 \times 10^7\) operations. Comfortable.

Edge Cases

Complete graph distances. If \(A[i][j] = 1\) for all \(i \neq j\), every edge is necessary (no bypass can improve on weight 1). The minimum graph is the complete graph with \(\binom{N}{2}\) edges, total weight \(\binom{N}{2}\).

Star graph distances. If \(A[0][j] = 1\) for all \(j\) and \(A[i][j] = 2\) for \(i, j \neq 0\), only the \(N-1\) edges from node 0 are necessary. Every pair \((i, j)\) with \(i, j \neq 0\) has a bypass through node 0: \(A[i][0] + A[0][j] = 1 + 1 = 2 = A[i][j]\).

Invalid matrix. \(A[0][1] = 1\), \(A[1][2] = 1\), \(A[0][2] = 5\). Triangle inequality violated: \(5 > 1 + 1\). Output \(-1\).

Exercises

  1. If the distance matrix represents a tree, how many edges will the reconstruction produce? Prove it.

  2. Can reconstruction produce a graph with more edges than the original? When?

  3. Given a distance matrix for a directed graph (\(A[i][j] \neq A[j][i]\) possible), how does the reconstruction change?

Problems

Problem Link Difficulty
ARC083-B -- Restoring Road Network atcoder.jp/contests/arc083/tasks/arc083_b Medium