UVa 10987

Summary

Given length of shortest path between every pair of vertices in an undirected graph with positive edge weights, construct such a graph, having minimum number of edges.

Explanation

Let the vertices be numbered from 1 to ${\displaystyle n}$, and let ${\displaystyle d_{ij}}$ be length of shortest path between ${\displaystyle i}$ and ${\displaystyle j}$.

First thing we need to do, is to check whether the graph actually exists, i.e. are the given ${\displaystyle d_{ij}}$'s lengths of shortest paths? If there exists three (distinct) vertices ${\displaystyle i}$, ${\displaystyle j}$, ${\displaystyle k}$, such that ${\displaystyle d_{ik}+d_{kj}, then obviously the graph doesn't exist, because by concatenating shortest paths from ${\displaystyle i}$ to ${\displaystyle k}$ and from ${\displaystyle k}$ to ${\displaystyle j}$ we get a path from ${\displaystyle i}$ to ${\displaystyle j}$, of length less than ${\displaystyle d_{ij}}$.

If no such vertices exist, then we can always construct a graph, an example is a complete graph ${\displaystyle K_{n}}$, with weight of edge ${\displaystyle (i,j)}$ equal to ${\displaystyle d_{ij}}$. However it has ${\displaystyle n(n-1)/2}$ edges, can we do better?

Consider some pair of vertices ${\displaystyle i}$ and ${\displaystyle j}$. Shortest path between them is either a single edge ${\displaystyle (i,j)}$ of weight ${\displaystyle d_{ij}}$, or a sequence of two or more edges each of weight strictly less than ${\displaystyle d_{ij}}$ (due to assumption, that weight of every edge is greater than zero.) In the latter case, there exists some vertex ${\displaystyle k}$, different from ${\displaystyle i}$ and ${\displaystyle j}$, such that ${\displaystyle d_{ik}+d_{kj}=d_{ij}}$. If no such ${\displaystyle k}$ exists, the only option is to include the edge ${\displaystyle (i,j)}$ to our graph. Otherwise we can always omit edge ${\displaystyle (i,j)}$ -- there has to be a path from ${\displaystyle i}$ to ${\displaystyle j}$ in the final graph through a sequence of edges of length less than ${\displaystyle d_{ij}}$ (this can be formally proven by induction on ${\displaystyle d_{ij}}$.)

An algorithm solving the problem follows (in pseudo-code).

```Input: n = number of vertices, d[i][j] = shortest path lengths' matrix.

for i = 1 to n
for j = 1 to n
for k = 1 to n
if d[i][k]+d[k][j] < d[i][j]:
return "Need better measurements."

for i = 1 to n
for j = 1 to n
flag = true
for k = 1 to n
if k != i and k != j and d[i][k]+d[k][j]==d[i][j]
flag = false
if flag = true:
add edge (i, j) of weight d[i][j] to the graph
```

```2
3
100
200 100
3
100
300 100```

Output

```Case #1:
2
1 2 100
2 3 100

Case #2:
Need better measurements.
```