I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper that I might as well share. I hope the combination of thread necromancy and self-promotion is forgivable.
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 answer is yes to both. Mohammad's algorithm definitely works, but there's a faster and more direct method that avoids the need to run cubic separation oracles. Let $H = (V, E, w')$ be an auxiliary undirected weighted graph, where the weight of each edge $e \in E$ is an integer indicating how many of the $n \choose 2$ paths taken on input contain that edge. Now, consider the edge-capacitated multicommodity flow instance over $H$ (interpreting edge weights as capacities) in which the goal is to simultaneously push 1 unit of flow between each pair of nodes. Obviously, this MC flow instance can be satisfied by pushing flow in the natural way along the paths given on input. As it turns out, one can prove that our $n \choose 2$ paths are unique shortest paths in some $G$ if and only if this is the unique way to satisfy the MC flow instance. We can test uniqueness by setting up an LP whose constraints are the usual ones for MC flow feasibility plus a certain carefully chosen objective function, and the edge weights of a satisfying $G$ can be extracted from the dual of this LP.
The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?
This condition is sometimes called "consistency" (a set of paths is consistent if the intersection of any two is a subpath of each). It follows from the above that consistency is not sufficient. One of the two tied-for-smallest counterexamples is the following color-coded system of four paths over six nodes:
In other words, there is no way to assign weights to the 8 edges pictured here so that all of these four paths are simultaneously the unique shortest path between their endpoints. However, any pair of them intersect on just one node, so they are consistent (even if we fill them out with a few additional paths in the right way to have $n \choose 2$ in total). There are infinitely many counterexamples like this one; see the paper for a characterization.
Three other quick comments on all this:
- The analogous statements that you might hope for all hold just fine in the setting of directed rather than undirected graphs,
- There is a nice topological interpretation of this theory that leads to some additional insights and intuitions about how unique shortest paths can be structured, and
- For some technical reasons, the theory simplifies conveniently in the setting of DAGs rather than undirected or (cyclic) directed graphs.