Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences of unweighted edges), but do not know $G$ itself. Can we produce any $G$ that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such $G$ exists?The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?
Axioms for Shortest Paths
graph theory;co.combinatorics;graph algorithms;metrics