多图和最便宜的路径(Multigraph and cheapest path)

多图和最便宜的路径(Multigraph and cheapest path)

我有一个问题要解决，我需要找到两个城市之间最便宜的路径，但是两个邻近城市之间有几条可能的路径，所以我有一个Multigraph，我可以在两个边缘之间有折扣。 是否有算法在Multigraph中找到最便宜的路径？

谢谢！

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!

最满意答案

Dijkstra使用Multigraphs，但你不应该跟踪被访问的顶点，你必须再次检查它们，因为平行边缘。 而且，每当你找到一个自循环时，你应该移动一个而不需要任何计算。

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.