algorithm - Dijkstra vs Bellman-ford 有向图会给出不同的结果

Question

我正在尝试学习图形，在其中我发现要找到从一个节点到另一个节点的最短路径，我们可以使用 Dijkstra 和 Bellman-ford 算法。

其中 Dijkstra 不适用于包含负权重边的图。而 Brllman-ford 可以处理这种包含负权重边的图。

我的疑问是我尝试了多种包含负权重边的图表并同时应用了 Dijkstra 和 Bellman-ford 但在所有情况下我发现相同的结果我的意思是没有区别，因为负权重边也 dijkstra 工作正常。可能是我的思维过程或我解决问题的方式是错误的，所以只有我得到了 dikstra 的正确答案。

我的问题是任何人都可以向我解释一个具有负边的图并解释 dijkstra 和 bellman-ford 的不同结果。

Answer 1

寻找两条边之间最短路径的 Djikstra 算法只能用于具有正权重的图。为了看bellman-ford和djikstra在边权为负的情况下给出的答案的差异，让我们举一个简单的例子

we have 3 nodes in the graph, A B C
A is connected to B edge weight 4
A is connected to C edge weight 2
B is connected to C edge weight -3

当使用djikstra计算A和C之间的最短路径时，我们得到权重2

但是当用bellman-ford计算A和C之间的最短路径时，权重为1

发生这种情况是因为 djikstra 最终确定了具有最小边权重的节点，而忽略了到该节点可能存在权重较小的路径这一事实(请注意，这只有在存在负权重时才会发生。与只有正权重这是不可能的)。

希望你明白其中的区别