具有平行边和自循环的 Dijkstra

Question

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

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

Answer 1

您可以轻松地将图形转换为没有单边循环和平行边的图形。

对于单边循环，您需要检查它们的权重是负数还是非负数。如果权重为负，则显然没有最短路径，因为您可以保持原地旋转并将路径长度减少到超出任何限制。但是，如果权重为正，则可以丢弃该边，因为没有最短路径可以通过该边。

零权重边会产生与任何零权重循环类似的问题：不会有一条而是无限多条最短路径，一遍又一遍地经过同一个循环。在这些情况下，明智的做法还是从图中删除边。

在平行边中，除了权重最小的边之外，您可以扔掉所有边。这样做的原因同样简单：如果有一条最短路径穿过边 A，而边 A 的平行边 B 具有较低的权重，您可以通过简单地替换 [=10 来构建更短的路径=] 和 B。因此没有最短路径可以通过 A.

Answer 2

如果您打算 运行 Dijkstra 算法而不对他的图做任何更改，您有可能 不会 获得源之间的最短路径和目的地。

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

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

Answer 3

它只需要一个小的变化。如果有多条边从 u 指向 v 并且每条边具有不同的权重，您可以：

1. 选择边缘最少的权重进行放松；或
2. 运行 每条边的松弛。

尽管#2 中的常数因子具有更高的值，但以上两者都具有相同的复杂性。

在任何情况下，您都需要确保在移动到下一个相邻节点之前评估 u 和 v 之间的所有边u.

的节点

Answer 4

我不认为它会产生任何类型的 problem.As dijkstra 算法将使用优先级队列，因此偏离最小值将首先得到更新。