将Dijkstra算法应用于负负无向图 [英] Apply Dijkstra's algorithm in a undirected graph with negative weights

问题描述

任何人都可以在权重为负的无向图中应用Dijkstra的算法吗？

Can anyone apply Dijkstra's algorithm in the undirected graph with negative weights above? Even if the algorithm fails.

邻接列表：

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)

推荐答案

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

Seed the traversal list with source node A, and it's cost with 0. Add an infinite cost for every other node:

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

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

Then take the lowest current cost item (I'll call it L) and "accept" it into the final cost set (the first pass case has L=source node (A), with a cost of 0). Check each edge from L calculating the total cost to follow that edge. If that total cost is less than the traversal list current cost, update the traversal list with the new lower cost.

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

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

C is now the lowest cost node in the traversal list, so accept C with a cost of 2:

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

在这一点上很容易发现问题，因为我只在遍历列表中放置了一个成本，该成本小于我刚刚节点的成本接受（C）。但是，我们不受理由或逻辑的束缚：

It's really easy to detect the problem at this point because I just put a cost in the traversal list that is less less than the cost of the node I just accepted (C). But, unencumbered by reason or logic we carry on:

{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}

由于图中的负成本循环，因此正确最终费用数组应为：

Due to the negative cost loops in the graph, the correct final cost array should be:

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

但是我们已经知道Dijkstra在图上失败了成本循环为负...对吧？

But we already knew that Dijkstra's fails when the graph has negative cost loops...right?

这篇关于将Dijkstra算法应用于负负无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！