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

Question

我需要找到一条通过无向图的最短路径，该无向图的节点是实数(正负)加权。这些权重就像是你进入节点可以获得或失去的资源。

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

例如考虑这样一个图:

A-start node; D-end node

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

最短路径是A-E-F-E-D

Dijkstra 算法本身并不能解决问题，因为它无法处理负值。于是，我想到了几个解决方案:

第一个使用Dijkstra算法计算每个节点到导出节点的最短路径长度，不考虑权重。这可以像 A* 中的某种启发式值一样使用。我不确定这个解决方案是否可行，而且成本非常高。我还考虑过实现 Floyd–Warshall 算法，但我不确定如何实现。

另一种解决方案是用不考虑权重的Dijkstra算法计算最短路径，如果计算出路径的资源总和后小于零，则遍历每个节点寻找一个可以快速增加资源总和的相邻节点，并且将它添加到路径中(如果需要多次)。如果存在足以增加资源总和但远离计算的最短路径的节点，则此解决方案将不起作用。

例如:

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

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

编辑:如果在计算最短路径时，您到达资源总和为零的点，则该路径无效，因为如果没有更多汽油。

Answer 1

编辑:我没有很好地阅读问题；该问题比常规的单源最短路径问题更高级。我暂时搁置这篇文章只是为了给您提供另一种您可能会觉得有用的算法。

Bellman-Ford algorithm解决单源最短路径问题，即使存在负权重边。但是，它不处理负循环(图中权重和为负的圆形路径)。如果您的图表包含负循环，您可能有麻烦了，因为我相信这会使问题成为 NP 完全问题(因为它对应于 longest simple path problem )。