8

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?

  • 1
    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
  • 1
    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
  • 1
    @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
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.