algorithm - 具有平行边和自循环的 Dijkstra

Question

如果我有一个没有负权重的加权无向图，但可以在顶点和自环之间包含多条边，我可以毫无问题地运行 Dijkstra 算法来找到源和目标之间的最小路径或存在反例吗？

我的猜测是没有问题，但我想确定一下。

Answer 1

如果您打算在不对图形进行任何更改的情况下运行 Dijkstra 算法，则有可能您不会获得源和目标之间的最短路径。

例如，考虑 S 和 O。现在，找到最短路径实际上取决于要将 O 插入队列时正在遍历的边。如果您的代码选择权重为 1 的边，则没有问题。但是，如果您的代码选择了权重为 8 的边，那么您的算法将会给出错误的答案。

这意味着算法的正确性现在取决于在源节点的邻接列表中输入边的顺序。