UVa 10987

From Algorithmist
Jump to: navigation, 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 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}}<d_{{ij}}, 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

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.