An algorithm for reconstructing a graph from its shortest path information?

Question

I have some shortest path data for a graph. Can I reconstruct the graph itself from this data?

More precisely, I have a boolean (0/1) matrix for each vertex v in graph (V, E). Matrix element [s,d] is equal to 1 iff v is in the shortest path from source vertex s to destination vertex d. All edges in the graph have the same length.

For example, for the graph

(V1) -- (V2) -- (V3)

the three matrices would be:

V1:

1 1 1
1 0 0
1 0 0

V2:

0 1 1
1 1 1
1 1 0

V3:

0 0 1
0 0 1
1 1 1

My questions:

1) is there an algorithm to reconstruct the set of edges E from these matrices?

2) is solution always unique? (this is more of a personal curiosity than a real requirement)

3) can the algorithm be generalized to nonuniform edge lengths?

• Giorgio: If there is an edge between two vertices v1 and v2, then exactly these two vertices are in the shortest path between v1 and v2. So for any other vertex v, [v1, v] == 0 == [v, v1] in the matrix of v2, and [v2, v] == 0 == [v, v2] in the matrix of v1.
• proskor: Maybe I am wrong, but arent 1) and 2) equivalent?
• Giorgio: I am not sure if 1) and 2) are equivalent: there might be more than one graph for a given shortest path information and also an algorithm that finds all possible solutions.
• proskor: Ok, but that's a different problem. The point was to reconstruct a graph from the set of these matrices, not to compute whether there is a solution which would satisfy the constrains encoded in these matrices.
• jk.: @Giorgio adding a single edge from v1 to v3 that is longer than v1-v2-v3 results in the same set of matrices unless I'm missing something - so would be a counterexample for the non-uniform edge case

Answer 1

you can extract the adjacency matrix by from the path matrices by using the following property.

There is a edge between 2 vertexes s and d if and only if the shortest path between them contains only s and d.

For non-uniform length you will only get the unique solution if the triangle inequality holds. Otherwise a graph with d(p1,p2)=1 d(p2,p3)=2 and d(p1,p3)=4 will show the shortest path between p1 and p3 as through p2 instead of the direct connection. Which means that the edge [p1,p3] will never be part of any shortest path.