algorithm - 在具有负权重的无向图中应用 Dijkstra 算法

Question

任何人都可以在上面具有负权重的无向图中应用 Dijkstra 算法吗？即使算法失败。

邻接名单：

A -> (B, 3), (C, 2), (D, 4)
B -> (A, 3), (C, -2), (F, 6)
C -> (A, 2), (B, -2), (E, 5)
D -> (A, 4), (E, 3), (F, 2)
E -> (C, 5), (D, 3), (F, -2)
F -> (B, 6), (D, 2), (E, -2)

Answer 1

使用源节点 A 播种遍历列表，其成本为 0。为每个其他节点添加无限成本：

{}, [A=0, B=inf, C=inf, D=inf, E=inf, F=inf]

然后取当前成本最低的项目（我将其称为 L）并将其“接受”到最终成本集中（第一个通过案例 L=源节点（A），成本为 0）。检查 L 中的每条边，计算遵循该边的总成本。如果该总成本小于遍历列表当前成本，则使用新的较低成本更新遍历列表。

{A=0}, [B=0+3, C=0+2, D=0+4, E=inf, F=inf]

C 现在是遍历列表中成本最低的节点，因此接受成本为 2 的 C：

{A=0, C=2}, [B=2-2=0, D=4, E=2+5=7, F=inf]

此时真的很容易检测到问题，因为我只是在遍历列表中放了一个小于我刚刚接受的节点的成本（C）的成本。但是，不受理性或逻辑的阻碍，我们继续：

{A=0, C=2, B=0}, [D=4, E=7, F=0+6]
{A=0, C=2, B=0, D=4}, [E=7, F=6]
{A=0, C=2, B=0, D=4, E=7}, [F=7-2=5]
{A=0, C=2, B=0, D=4, E=7, F=5}

由于图中的负成本循环，正确的最终成本数组应该是：

{A=-inf, B=-inf, C=-inf, D=-inf, E=-inf, F=-inf}

但是我们已经知道，当图表具有负成本循环时，Dijkstra 会失败……对吗？