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?

Improve this question
10
  • 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
    Commented Jul 7, 2014 at 12:30
  • 1
    Maybe I am wrong, but arent 1) and 2) equivalent?
    – proskor
    Commented 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.
    – Giorgio
    Commented 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.
    – proskor
    Commented Jul 7, 2014 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.
    Commented Jul 7, 2014 at 12:56

1 Answer 1

Reset to default
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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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