logo标签列表

迪杰斯特拉算法无法处理负权重，你在现实世界中何时看到负权重？

graphdijkstra
3

我想不出在哪种情况下会有负权重。两个房子之间的距离不能为负，时间也不能倒流。什么时候会有一个带负边权重的图？

我发现Bellman-Ford算法最初用于处理ARPANET中的路由问题，但我仍然无法想象你会遇到具有负权重的路线，这似乎是不可能的。我可能只是想得太多了，你能举一个简单的例子吗？

由于w = m * a，如果你处于负加速度下（即减速），你会感到负重量。或者我是否对你的问题过于字面理解了... - cusimar9
2
如果你正在减速或边缘代表金钱，那么你可能会有一条负路径。这更有意义。我的所有示例都非常具体，然后它们引入了负权重，而我没有从其他角度考虑。我想边缘也可以是金钱，所以一堆路径赚钱，然后一条路径亏钱。 - chum of chance
我认为这个关于金钱的例子很值得思考；但是，在那种情况下，你不会只是在使用 Dijkstra 算法遍历图之前从中删除所有亏损的路径吗？是否有任何方法可以得到一个最优解，其中包含一条亏损的路径？ - Dave
2
@Dave：当然。负值边可能是通往非常高回报子图的唯一路径。 - Jim Mischel
@Jim - 是的，我刚刚弄明白了并编辑了我的答案；但你比我更快。 - Dave
5个回答
13

假设走一定距离需要一定数量的食物。但是沿着某些路径有可以采集的食物，因此通过遵循这些路径，您可能会获得食物。

2

在进行路由时，可能会给一个链接分配负权重，使其成为默认路径。如果你有一条主线路和备用线路，并且出于某种原因不想在它们之间进行负载均衡，可以使用这种方式。

我认为这是一个很好的观点。但在这种情况下，负权重实际上并不代表负路径权重。这更像是有时人们将值初始化为-1，然后执行if(foo >= 0) { bar(); }。如果这是C实现，我可以看到它被广泛地用于使路径成为默认路径。 - Dave
当你处理路由协议时，你可以设置链接权重（路径权重）来强制协议按照你的意愿进行。我不知道为什么会将链接权重设置为负数，但这是可能的。 - Nik
1

即使有一个例子，你也可以将其规范化为全部为正数。任何负重的实际表示都是相对于某个0的。我的意思是，可能没有使用纯正数权重无法完成的负权重应用。

编辑：经过进一步思考，我想你可能会遇到某些路径具有负权重的情况。在这种情况下，假设负权重是不好的，你必须有这样一种情况，即实现到达所需终点的唯一可能方式是，在图形中至少有一个点是必须采取负路径的（也就是说，没有其他选项可达到目标）。但是，如果图形尚未被遍历，你怎么知道它是真的呢？

编辑（再次）：@Jim，我认为你是对的。瓶颈并不是很相关。我想我太快就假设了它是因为引入负边缘时会出现一个问题 - 如果可以在不经过任何负边缘的情况下遍历图形，则首先负边缘有什么作用？但是，这并不是很好，因为除了事后之外，您怎么知道是否可以穿越图形而不越过负边缘？

另外值得注意的是，根据Djikstra算法的维基百科页面：

Dijkstra算法由荷兰计算机科学家Edsger Dijkstra于1956年构思，并于1959年发表，是一种图形搜索算法，可解决具有非负边缘路径成本的图形的单源最短路径问题，生成最短路径树。该算法通常用于路由，并用作其他图形算法的子程序。

所以，尽管这次对话很有用且发人深省；也许问题的标题应该是“遍历带有负边的图的正确算法是什么？”Djikstra算法旨在找到最短路径。但是，如果引入正权重和负权重，那么目标是否从寻找最短路径变为寻找最积极的路径——而不管你选择的路径上有多少条边呢？如果是这样，那么你的退出条件是什么？你唯一能知道你已经达到最优解的方法就是如果你碰巧遇到了一条包含所有正边而没有任何负边的路径——而这种情况只会偶然发生吧？因此，如果引入正权重和负权重的情况下将目标更改为最积极的（或者根据你想要表述的方式是最消极的），那么这个问题是否注定要O(n!)，因此最好通过决策算法（如alpha/beta）来解决，该算法将在允许您采取的总边数受限制的情况下产生最佳结果？

为什么负边缘是瓶颈？考虑从0点开始，找到一条通过图形的路径，使得得分最高。每个边缘都可以增加或减少您的得分。如果权重是常数，则您的归一化方法应该有效。如果权重可以改变……那就是完全不同的问题了，不是吗？ - Jim Mischel
将“最短”替换为“最小成本”，这样更有意义。 - Jim Mischel
“最小成本”是指最接近于零吗？ - Dave
是的。例如，考虑旧游戏文明II，在那里你可以在道路上移动，每个方格消耗1/3的移动点，或者在铁路上移动（如果你已经建造了它们），每个方格消耗0个移动点。铁路路径可能会更长（即访问更多节点），但成本比在道路上移动任何距离要少。 - Jim Mischel
参考文献，将负边权转换为正数的算法是约翰逊算法的一部分；它需要支持负边权的单源最短路径计算作为预处理步骤。您可以使用它来计算所有对最短路径，以便大多数源可以使用Dijkstra算法。 - Jeremiah Willcock
1

我猜你可能会遇到负权重的情况，尤其是在已经有非负权重系统的情况下，如果出现一条比所有现有路径更便宜的路径，而且由于某种原因重新调整网络的成本很高。

0

如果你正在尝试找到在水上乐园中游过一系列相连的泳池的最快方法，并且它有滑道。

1
回程时间的水槽…… - Tom Anderson
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接