# Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights.

The only thing I can think of is using Dijkstra on each graph separately, but I was wondering if there is a way to take advantage of the isomorphism for a faster algorithm.

• I'm sure that it's easy to construct examples of isomorphic graphs with very different shortest paths, so I doubt that it's possible to always interleave computations. Maybe some preprocessing is possible. – Raphael Sep 29 '16 at 8:57
• Take complete graphs on $n$ vertices. By setting some edge weights to infinity and others to 1 you can recreate any graph on $n$ vertices, as far as shortest paths are concerned. – adrianN Sep 29 '16 at 9:53