Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

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