The problem can be represented as a graph in which vertices correspond to cities and edges correspond to phone lines. In this representation, the problem can be formulated as follows:
We are given an N×N matrix A of positive numbers and a positive integer E (in fact, we are given just half of A, but the matrix is symmetric and all elements on the diagonal are unimportant). We have to determine, whether it is possible to find a graph with N vertices and E edges (each edge must have a positive length) that satisfies the condition C: "matrix element A[I,J] is the length of shortest path beween vertices I and J".
We will try to find a graph G satisfying C with the least number L of edges. It is clear that once this is done it is possible to add more edges with really large weights without changing the lengths of shortest paths. Thus the answer is "YES" for all values of E between L and N*(N-1)/2.
Our algorithm works like this:
Clearly, this algorithm runs in O(N^{4}) time and O(N^{2}) space.
Denote G_{S} a graph that is obtained by our algorithm just after processing all entries of A[i,j]≤S. We will show that each graph G_{S} has the following two properties:
Clearly, if Q is the largest element in matrix A, then P(Q) is exactly the property C, and L(Q) implies that G_{Q} has the least possible number of edges. In other words, graph G_{Q}, obtained when our algorithm is finished, indeed satisfies the requirements of the problem.
We will prove our claim by induction on S (where S is a value taken from the matrix A or 0). Base case: Graph G_{0} has no edges. Clearly, this graph satisfies property P(0) and L(0).
Inductive step: Assume that graph G_{S'} satisfies P(S') and L(S') and let S be the smallest entry from A larger than S'. We will show that G_{S} also satisfies properties P(S) and L(S).
We obtained graph G_{S} by adding several edges of weight S to graph G_{S'}. An edge was added between pair of vertices I,J if and only if A[I,J]=S, and the length of the shortest path between I and J in G_{S'} was longer than S. Since G_{S'} satisfies P(S'), it is easy to see that G_{S} must satisfy P(S).
It remains to show that G_{S} also satisfies L(S). Let us assume that there is an edge (I,J) in G_{S} such that there exists a graph H satisfying P(S) where I and J are not connected.
Thus, G_{S} satisfies L(S).
We have proved that if the algorithm produces graph G_{Q}, the graph satisfies properties P(Q) and L(Q). It is also possible that the algorithm will fail while producing graph G_{S} from G_{S'}. This is because the for some edge (I,J), the graph G_{S'} already contained a path shorter than A[I,J]. Property L(S') implies that the correct answer is indeed "NO" in this case.