10987 - AntiFloyd
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.
Let the vertices be numbered from 1 to , and let be length of shortest path between and .
First thing we need to do, is to check whether the graph actually exists, i.e. are the given 's lengths of shortest paths? If there exists three (distinct) vertices , , , such that , then obviously the graph doesn't exist, because by concatenating shortest paths from to and from to we get a path from to , of length less than .
If no such vertices exist, then we can always construct a graph, an example is a complete graph , with weight of edge equal to . However it has edges, can we do better?
Consider some pair of vertices and . Shortest path between them is either a single edge of weight , or a sequence of two or more edges each of weight strictly less than (due to assumption, that weight of every edge is greater than zero.) In the latter case, there exists some vertex , different from and , such that . If no such exists, the only option is to include the edge to our graph. Otherwise we can always omit edge -- there has to be a path from to in the final graph through a sequence of edges of length less than (this can be formally proven by induction on .)
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
Case #1: 2 1 2 100 2 3 100 Case #2: Need better measurements.