我有一个有向的正加权图。每个边缘都有使用成本。我只有 A 钱，我想用 dijkstra 算法计算最短路径，但路线上的边成本总和必须小于或等于 A。
我想用最小的 Dijstra 修改来做到这一点（如果我可以用 Dijkstra 的小修改来做到这一点）。如果可以的话，我必须这样做O(n*log(n))，但我想我可以。
任何人都可以帮助我吗？
问问题
4852 次
2 回答
6
于 2010-04-28T05:42:49.293 回答
0
您实际上不需要修改 Dijkstra 的算法来执行此操作，因为答案相当于找到最短路径，然后在小于或等于 A 时接受它。
当然，如果您访问成本高于 A 的路径，您总是可以短路内部循环。
编辑：通过澄清您希望最大限度地减少成本和距离，如果不澄清您想要的解决方案，您将无法做到这一点。你想要最便宜的路径吗？你想要最短的路径吗？你想要一些成本和距离的函数吗？所有这些都决定了您应该对特定边缘使用什么加权函数。
于 2010-04-26T01:05:45.627 回答