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?
10
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.