Dijkstra最短路径算法与边权相关

Question

9

我有一个有向的、正加权图。每条边都有使用成本。我只有 A 元钱，我想用 Dijkstra 算法计算最短路径，但是路径上所有边的成本之和必须小于或等于 A。

如果可以的话，我希望用最小的 Dijkstra 修改来实现这个目标。如果可以的话，我希望在 O(n*log(n)) 的时间复杂度内完成，但我认为这是可能的。

有人能帮我吗？

- Svisstack

3

通常在作业问题中，你已经有了什么样的内容？ - Stephen

我是否正确理解问题：每条边都有长度和成本，您希望最小化长度，并附加约束条件是成本必须小于或等于A。 - Mark Byers

@IVlad：如果你能在O(n*log(n))的复杂度下不使用Dijkstra算法完成这个任务，那么你真的很厉害；-) 但我认为你不能在线性对数时间内完成而不使用Dijkstra。 - Svisstack

请问您能提供SPOJ问题的链接吗？ - IVlad

@IVlad：http://www.spoj.pl/problems/ROADS/ - Svisstack

显示剩余5条评论

2个回答

0

你其实不需要修改 Dijkstra 算法来实现这个，因为答案等同于找到最短路径，然后如果它小于或等于 A，则接受它。

当然，如果你访问的路径成本大于 A，你可以始终短路内部循环。

编辑：根据你想要最小化成本和距离的澄清，如果没有明确你想要的解决方案，你无法做到这一点。你想要最便宜的路径吗？你想要最短的路径吗？你想要某些成本和距离的函数吗？所有这些都确定了你应该为特定边使用什么加权函数。

- MSN

边的费用和长度是两种不同的东西，请查看注释。 - michalburger1

1

@Bus 他的问题中没有提到长度。据我理解，每条边关联的唯一值是成本。 - Enrique

Svisstack的许多含义，即使在他回答马克的问题后，对我仍然不清楚。 - outis

1

我认为讨论已经很清楚了。马克问道：“每条边都有一个长度和成本，你想最小化长度并附加约束的成本必须小于或等于A。” Svisstack回答说是的。 - michalburger1

1

@Bus：只是有时候会有人不理解澄清问题的意思，或者问题中的替代含义和歧义，并非第一次出现这种情况。 - outis

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

这个问题是在 CEOI '98 上提出的，官方解决方案可以在此处找到。