对于通过实加权无向图的单对最短路径,最简单的算法/解决方案是什么？

Question

我需要通过无向图找到最短路径,其节点是实数(正和负)加权.这些权重就像您可以通过输入节点获得或松散的资源.

路径的总成本(资源总和)不是很重要,但必须大于0,并且长度必须尽可能短.

例如,考虑如下图:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

最短的路径是AEFED

Dijkstra的算法本身并不起作用,因为它无法处理负值.所以,我想了几个解决方案:

首先使用Dijkstra算法计算从每个节点到出口节点的最短路径的长度,而不考虑权重.这可以像A*中的某种启发式值一样使用.我不确定这个解决方案是否可行,而且成本也很高.我也想过实现Floyd-Warshall的算法,但我不确定如何.

另一种解决方案是计算与Dijkstra算法不考虑权重的最短路径,如果计算路径的资源总和后,是小于零,经过的每个节点找到可能会很快增加资源和邻近节点,并将其添加到路径(如果需要,可以多次).如果有一个节点足以增加资源总和,但距计算的最短路径更远,则此解决方案将不起作用.

例如:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

你能帮我解决这个问题吗？

编辑:如果在计算最短路径时,您到达资源总和等于零的点,该路径无效,因为如果没有更多的汽油则无法继续.

Answer 1

这似乎不是一个优雅的解决方案，但考虑到创建循环路径的能力，我看不到解决办法。但我只会迭代地解决它。使用第二个示例 - 从 A 处的点开始，为其指定 A 的值。移动一“转” - 现在我有两个点，一个在 B 处，值为 5，另一个在 D 处，值为 5。再次移动 - 现在我有 4 个点要跟踪。C：45，A：15，A：15，E：0。可能E处的那个可以振荡并变得有效，所以我们还不能把它扔掉。移动和积累等。第一次到达具有正值的结束节点时，您就完成了（尽管同一回合可能有其他等效路径进入）

显然有问题，因为要跟踪的点数会很快增加，并且我假设您的实际图表比示例复杂得多。