Axioms for Shortest Paths
You can write the problem as an LP, can't you?  For any two vertices u, v, and any path P from u to v, the weight of P is greater than or equal to the weight of the given shortest path between u and v. These are all linear inequalities, and even though there are exponentially many, the separation problem is in P (it's just an all-pairs shortest path problem).  So, you can use the Ellipsoid algorithm to solve it.