Dijkstra具有平行边缘和自循环

Question

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

我的猜测是没有问题,但我想确定.

Answer 1

如果您要运行Dijkstra的算法而不对图形进行任何更改，则有可能无法获得源与目标之间的最短路径。

例如，考虑S和O。现在，查找最短路径实际上取决于要将O推入队列时要遍历的边。如果您的代码选择权重为1的边缘，就可以了。但是，如果您的代码选择权重为8的边缘，那么您的算法将为您提供错误的答案。

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