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

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?

• 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. – Giorgio Jul 7 '14 at 12:30
• Maybe I am wrong, but arent 1) and 2) equivalent? – proskor Jul 7 '14 at 12:31
• 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. – Giorgio Jul 7 '14 at 12:37
• 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. – proskor Jul 7 '14 at 12:42
• @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 – jk. Jul 7 '14 at 12:56