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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Sep 29 '16 at 8:57
  • 4
    $\begingroup$ 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. $\endgroup$
    – adrianN
    Sep 29 '16 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.