algorithm - 多图和最便宜的路径

Question

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

谢谢！

Answer 1

Dijkstra 与 Multigraphs 一起工作，但您不应该跟踪访问过的顶点，由于平行边，您必须再次检查它们。此外，无论何时你发现一个自环，你都应该移动一个而无需任何计算。