Dijkstra算法中的平行边和自环问题

Question

11

如果我有一个带权无向图，但可能包含顶点之间的多个边和自环，是否可以运行Dijkstra算法来找到源点和目标点之间的最短路径，或者存在反例？

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

- Manuel

1

就像答案所提到的，这真的取决于Dijkstra算法的具体实现。这个实现会很好地工作，因为它将所有可能的平行边中最小的边添加到您正在使用的数据结构中，以跟踪尚未探索的节点。 - thebenman

5个回答

4

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

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

零权重边缘会产生与任何零权重循环相似的问题：不仅有一个而是无限数量的最短路径，反复通过同一个循环。在这些情况下，明智的做法是从图中删除边缘。

对于平行边缘，您可以丢弃除最低权重边缘外的所有边缘。这样做的原因同样简单：如果存在一条通过具有较低权重的平行边缘B的边缘A的最短路径，则可以通过简单地用B替换A来构造更短的路径。因此，没有最短路径可以通过A。

- biziclop

好的，那听起来不错。但我的问题是：如果我在该图上运行Dijkstra算法而没有进行任何修改，会出现问题吗？ - Manuel

1

@Manuel 这完全取决于实现方式。例如，在计算节点 N 到其所有邻居的距离的步骤中，某个实现可能会假设从 N 出发的每条出边都指向不同的节点，因此它可能会将结果存储在一个以节点为键的映射中。在这种情况下，平行边很容易导致错误的结果。 - biziclop

3

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

以上两种方法的复杂度相同，尽管#2中的常数因子值更高。

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

- lalatnayak

1

我不认为这会产生任何问题。因为Dijkstra算法将使用优先队列，所以最小值肯定会首先得到更新。

- ankitssingh26

0

在您的示例中，从节点S到O，对于Dijkstra算法，这取决于您的图形表示。在创建图形时，对于此算法和其他最短路径算法，您只需要考虑最低加权边，因此在创建图形结构时，仅存储具有最低值的边缘。然后，您可以按预期运行Dijkstra算法。

- raiyan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- attaboy182 · Accepted Answer

如果你运行Dijkstra算法而不对图进行任何更改，那么有可能你将无法得到源点和目标点之间的最短路径。

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

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