# 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 $n$ , and let $d_{ij}$ be length of shortest path between $i$ and $j$ .

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

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

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