Search code examples
algorithmgraphshortest-path

Multigraph and cheapest path

I have a problem to solve, I need to find the cheapest path between two cities, but there are several possible path between two neighboring cities so I have a Multigraph and i can have discount between two edge . Is there an algorithm to find the cheapest path in a Multigraph?

thanks!

Solution

  • Dijkstra works with Multigraphs, but you should not keep track of visited vertices, you have to examine them again because of the parallel edges. Moreover, whenever you find a self-loop you should move one without any calculations.