带边成本的 Dijkstra 最短路径算法
我有一个有向正加权图。每条边都有使用成本。 我只有 A 钱，我想用 dijkstra 算法计算最短路径，但路线上的边成本总和必须小于或等于 A。
我想用最小的 Dijstra 修改来做到这一点（如果我可以用小的修改来做到这一点）迪杰斯特拉）。如果可以的话，我必须在 O(n*log(n)) 内完成此操作，但我认为我可以。
任何人都可以帮我解决这个问题吗？
I have a directed, positive weighted graph. Each edge have a cost of use.
I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A.
I want to do this with most smallest Dijstra modification (if I can do it with small modification of Dijkstra). I must do this in O(n*log(n)) if I can, but i think i can.
Anyone can help me with this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
https://www.spoj.pl/problems/ROADS/
该问题位于CEOI '98 及其官方解决方案可以在 CEOI '98 找到。 hsin.hr/ceoi98/solutions/roads.c" rel="nofollow noreferrer">此处。
https://www.spoj.pl/problems/ROADS/
The problem was given at CEOI '98 and its official solution can be found here.
你实际上不需要修改 Dijkstra 算法来做到这一点，因为答案相当于找到最短路径，然后如果它小于或等于 A 则接受它。
当然，如果你访问，你总是可以短路内部循环成本大于 A 的路径。
编辑：明确您希望最小化成本和距离，如果不明确您想要的解决方案，您就无法做到这一点。您想要最便宜的路径吗？你想要最短路径吗？你想要一些成本和距离的函数吗？所有这些都决定了您应该对特定边缘使用什么加权函数。
You don't really need to modify Dijkstra's algorithm to do this as the answer is equivalent to finding the shortest path and then accepting it if it's less than or equal to A.
Of course, you could always short circuit the inner loop if you visit a path with a cost more than A.
EDIT: With the clarification that you want to minimize cost AND distance, you can't do that without clarifying the solution you want. Do you want the cheapest path? Do you want the shortest path? Do you want some function of cost and distance? All of these determine what weighting function you should use for a particular edge.