graph - Dijkstra 的算法无法处理负权重，你在现实世界中什么时候看到负权重？

Question

我想不出一个具体的例子，在这种情况下你的体重是负的。你不能在两所房子之间有负距离，你不能及时回到过去。你什么时候会有一个负边权重的图？

我发现 Bellman Ford 算法最初用于处理 ARPANET 中的路由，但同样无法想象你会在哪里遇到负权重的路由，这似乎是不可能的。我可能只是想得太多了，一个简单的例子是什么？

Answer 1

假设步行一段距离需要一定量的食物。但是在某些路径上，您可以收集食物，因此您可以通过沿着这些路径获得食物。

Answer 2

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

Answer 3

即使有一个例子；您可能可以将其标准化为全部积极。负权重的任何实际表示都与某个 0 相关。我想我要说的是，可能没有负权重的应用不能仅使用正权重来完成。

编辑：在考虑了更多之后，我想您可能会遇到给定路径具有负权重的情况。在这种情况下；假设负权重不好，您将不得不遇到这样一种情况，即实现到达所需端点的目标的唯一可能方法意味着您的图表中必须至少有一个点需要您采取负面路径（如，没有其他选择可以达到您的目标）. 但我想如果没有遍历图表；你怎么知道这是真的？

编辑（再次）：@Jim，我认为你是对的。阻塞点并不真正相关。我想我太快假设这是因为在引入负边时我想到的一个问题是 - 如果可以在不采用任何负边的情况下遍历图形，那么第一个负边在做什么地方？但是，这不是很好，因为——事后看来——你怎么知道一个图是否可以在不越过负边的情况下被遍历？

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

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

因此，即使这次谈话很有用且发人深省；也许问题的标题应该是“用于遍历具有负边的图的正确算法是什么？” Djikstra 的算法旨在找到最短路径。但是，如果您引入正权和负权重，那么无论您选择的路径上有多少条边，目标不会从寻找最短路径变为找到最正面的路径吗？如果是这样，你的退出条件是什么？您可以知道您已达到最佳解决方案的唯一方法是，如果您遇到的路径包含所有正边缘而没有任何负边缘 - 并且不会 这种情况只是偶然发生的吗？所以 - 如果引入一个有正负权重的情况将目标改变为最积极的（或消极的，取决于你想如何构建它）不会这个问题注定要 O(n!) 并且因此是最好的由决策算法（如阿尔法/贝塔）解决，在限制您允许采用的边总数的情况下，该算法会产生最佳结果？

Answer 4

我猜你可能会得到负权重，因为你已经有了一个非负权重的系统，并且出现的路径比所有现有路径都便宜，并且由于某种原因，重新加权网络的成本很高。

Answer 5

如果你想找到最快的方式在水上公园的一系列相连的游泳池中游泳，它有水槽。