UVa 10987

From Algorithmist
Jump to navigation Jump to search

10987 - AntiFloyd[edit]

Summary[edit]

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[edit]

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

Input[edit]

2
3
100
200 100
3
100
300 100

Output[edit]

Case #1:
2
1 2 100
2 3 100

Case #2:
Need better measurements.