# 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`. Jul 7, 2014 at 12:30
• Maybe I am wrong, but arent 1) and 2) equivalent? Jul 7, 2014 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. Jul 7, 2014 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. Jul 7, 2014 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, 2014 at 12:56

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.