通过实加权无向图的单对最短路径的最简单算法/解决方案是什么？
我需要找到一条通过无向图的最短路径，其节点是实数（正和负）加权的。这些权重就像您可以通过进入节点获得或失去的资源。
路径的总成本（资源总和）不是很重要，但它必须大于 0，并且长度必须尽可能短。
例如，考虑这样的图：
A-start node; D-end node
A(+10)--B( 0 )--C(-5 )
\ | /
\ | /
D(-5 )--E(-5 )--F(+10)
最短路径是 AEFED
Dijkstra 算法，单独使用并不能解决问题，因为它无法处理负值。于是，我想了几个解决方案：
第一个使用Dijkstra算法计算从每个节点到出口节点的最短路径的长度，不考虑权重。这可以像 A* 中的某种启发式值一样使用。我不确定这个解决方案是否可行，而且成本非常高。我也考虑过实现弗洛伊德-沃歇尔算法，但我不知道如何实现。
另一种解决方案是使用Dijkstra算法计算最短路径，不考虑权重，如果计算出路径的资源总和小于零，则遍历每个节点找到可以快速增加资源总和的邻居节点，并将其添加到路径（如果需要的话多次）。如果有一个节点足以增加资源总量，但距离计算出的最短路径较远，则该解决方案将不起作用。
例如：
A- start node; E- end node
A(+10)--B(-5 )--C(+40)
\
D(-5 )--E(-5 )
你能帮我解决这个问题吗？
编辑：如果在计算最短路径时，您到达资源总和等于零的点，则该路径无效，因为如果没有更多汽油，您将无法继续前进。
I need to find a shortest path through an undirected graph whose nodes are real (positive and negative) weighted. These weights are like resources which you can gain or loose by entering the node.
The total cost (resource sum) of the path isn't very important, but it must be more than 0, and length has to be the shortest possible.
For example consider a graph like so:
A-start node; D-end node
A(+10)--B( 0 )--C(-5 )
\ | /
\ | /
D(-5 )--E(-5 )--F(+10)
The shortest path would be A-E-F-E-D
Dijkstra's algorithm alone doesn't do the trick, because it can't handle negative values. So, I thought about a few solutions:
First one uses Dijkstra's algorithm to calculate the length of a shortest path from each node to the exit node, not considering the weights. This can be used like some sort of heuristics value like in A*. I'm not sure if this solution could work, and also it's very costly. I also thought about implement Floyd–Warshall's algorithm, but I'm not sure how.
Another solution was to calculate the shortest path with Dijkstra's algorithm not considering the weights, and if after calculating the path's resource sum it's less than zero, go through each node to find a neighbouring node which could quickly increase the resource sum, and add it to the path(several times if needed). This solution won't work if there is a node that could be enough to increase the resource sum, but farther away from the calculated shortest path.
For example:
A- start node; E- end node
A(+10)--B(-5 )--C(+40)
\
D(-5 )--E(-5 )
Could You help me solve this problem?
EDIT: If when calculating the shortest path, you reach a point where the sum of the resources is equal to zero, that path is not valid, since you can't go on if there's no more petrol.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
编辑：我没有很好地阅读这个问题；该问题比常规的单源最短路径问题更高级。我暂时保留这篇文章只是为了给您提供另一种可能对您有用的算法。
Bellman-Ford 算法解决了单源最短路径问题，即使存在具有负权重的边。但是，它不处理负循环（图中权重总和为负的圆形路径）。如果你的图表包含负循环，你可能会遇到麻烦，因为我相信这使得问题 NP 完全（因为它对应于 最长简单路径问题）。
Edit: I didn't read the question well enough; the problem is more advanced than a regular single-source shortest path problem. I'm leaving this post up for now just to give you another algorithm that you might find useful.
The Bellman-Ford algorithm solves the single-source shortest-path problem, even in the presence of edges with negative weight. However, it does not handle negative cycles (a circular path in the graph whose weight sum is negative). If your graph contains negative cycles, you are probably in trouble, because I believe that that makes the problem NP-complete (because it corresponds to the longest simple path problem).
这似乎不是一个优雅的解决方案，但考虑到创建循环路径的能力，我看不到解决办法。但我只会迭代地解决它。使用第二个示例 - 从 A 处的点开始，为其指定 A 的值。移动一“转” - 现在我有两个点，一个在 B 处，值为 5，另一个在 D 处，值为 5。再次移动 - 现在我有 4 个点要跟踪。 C：45，A：15，A：15，E：0。可能E处的那个可以振荡并变得有效，所以我们还不能把它扔掉。移动和积累等。第一次到达具有正值的结束节点时，您就完成了（尽管可能有其他等效路径在同一回合中进入）
显然是有问题的，因为要跟踪的点数会相当多地增加很快，我假设您的实际图表比示例复杂得多。
This doesn't seem like an elegant solution, but given the ability to create cyclic paths I don't see a way around it. But I would just solve it iteratively. Using the second example - Start with a point at A, give it A's value. Move one 'turn' - now I have two points, one at B with a value of 5, and one at D also with a value of 5. Move again - now I have 4 points to track. C: 45, A: 15, A: 15, and E: 0. It might be that the one at E can oscillate and become valid so we can't toss it out yet. Move and accumulate, etc. The first time you reach the end node with a positive value you are done (though there may be additional equivalent paths that come in on the same turn)
Obviously problematic in that the number of points to track will rise pretty quickly, and I assume your actual graph is much more complex than the example.
我会像 Mikeb 建议的那样进行类似的操作：对可能状态的图（即（位置，燃料左）对）进行广度优先搜索。
使用示例图：
广度优先搜索此图保证为您提供实际到达目标的最短路线如果存在这样的路线。如果没有，您将不得不在一段时间后放弃（在搜索了 x 个节点之后，或者当您到达一个分数大于所有负分数总和的绝对值的节点时），因为该图可能包含无限循环。
如果您也想找到最便宜的路径（燃料方面），则必须确保在找到目标后不要立即中止，因为您可能会找到多个相同长度但成本不同的路径。
I would do it similarly to what Mikeb suggested: do a breadth-first search over the graph of possible states, i.e. (position, fuel-left)-pairs.
Using your example graph:
Searching this graph breadth-first is guaranteed to give you the shortest route that actually reaches the goal if such a route exists. If it does not, you will have to give up after a while (after x nodes searched, or maybe when you reach a node with a score greater than the absolute value of all negative scores combined), as the graph can contain infinite loops.
You have to make sure not to abort immediately on finding the goal if you want to find the cheapest path (fuel wise) too, because you might find more than one path of the same length, but with different costs.
尝试将最小权重的绝对值（在本例中为 5）添加到所有权重中。这将避免负循环路径
当前的最短路径算法需要计算到每个节点的最短路径，因为它会组合某些节点上的解决方案，这将有助于调整其他节点中的最短路径。没有办法让它只适用于一个节点。
祝你好运
Try adding the absolute value of the minimun weight (in this case 5) to all weights. That will avoid negative ciclic paths
Current shortest path algorithms requires calculate shortest path to every node because it goes combinating solutions on some nodes that will help adjusting shortest path in other nodes. No way to make it only for one node.
Good luck