Dijkstra算法无法处理负权重，你什么时候在现实世界中看到负权重？
我想不出体重为负的具体例子。两栋房子之间的距离不能为负，你不能回到过去。什么时候你会得到一个带有负边权重的图？
我发现贝尔曼·福特算法最初是用来处理阿帕网中的路由的，但同样，无法想象你会在哪里遇到负权重的路由，这似乎是不可能的。我可能想得太仔细了，一个简单的例子是什么？
I can't think of a concrete instance in which you'd have a negative weight. You cannot have a negative distance between two houses, you cannot go back in time. When would you have a graph with a negative edge weight?
I found the Bellman Ford algorithm was originally used to deal with routing in ARPANET, but again, can't imagine where you'd run into a route with a negative weight, it just doesn't seem possible. I could just be thinking too hard about this, what would be a simple example?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
假设步行一段距离需要一定量的食物。但沿着某些路径，你可以收集食物，所以你可以通过沿着这些路径获得食物。
Suppose that walking a distance takes a certain amount of food. But along some paths there is food you can gather, so you might gain food by following those paths.
进行路由时，可能会为链路分配负权重，使其成为默认路径。如果您有主线路和备用线路，并且出于某种原因您不想在它们之间进行负载平衡，则可以使用此功能。
When doing routing, a negative weight might be assigned to a link to make it the default path. You could use this if you have a primary and a backup line and for whatever reason you don't want to load balance between them.
我猜你可能会得到负权重，因为你已经有了一个具有非负权重的系统，并且出现了一条比所有现有路径更便宜的路径，并且由于某种原因，重新加权网络的成本很高。
I guess you might get negative weights where you've already got a system with non-negative weights and a path comes along that is cheaper than all existing paths, and for some reason it's expensive to reweight the network.
即使有例子；你也许可以将其正常化为积极的。负权重的任何实际表示都是相对于某个 0 的。我想我想说的是，负权重的应用可能无法完全使用正权重来完成。
编辑：在更多地考虑这一点之后，我想您可能会遇到给定路径具有负权重的情况。在此背景下；假设负权重不好，
您将不得不遇到一种情况，即实现达到所需终点的目标的唯一可能方法意味着您的图表中必须至少有一个点，您'需要采取负面路径（例如，没有其他选项可以实现您的目标）。但我想如果图还没有被遍历过；你怎么知道这是真的？编辑（再次）：@Jim，我认为你是对的。瓶颈并不真正相关。我想我太快地假设这是因为在引入负边时我脑海中浮现的一个问题是 - 如果可以在不采用任何负边的情况下遍历图形，那么第一个负边在做什么地方？但是，这不太成立，因为——事后看来——你怎么知道一个图是否可以在不跨越负边的情况下被遍历？
另外值得注意的是，根据 Djikstra 算法的维基百科页面：
因此，尽管这次谈话很有用且发人深省；也许问题的标题应该是“用于遍历具有负边的图的正确算法是什么？” Djikstra 的算法旨在找到最短路径。但是，如果您引入正权重和负权重，那么目标是否会从寻找最短路径变为寻找最正权重 - 无论您选择的路径上有多少条边？如果是的话，你的退出条件是什么？您可以知道自己已经达到最佳解决方案的唯一方法是，如果您碰巧遇到一条包含所有正边而没有任何负边的路径 - 这种情况难道不是偶然发生的吗？因此，如果引入一种存在正权重和负权重的情况，将目标更改为最正的（或负的，具体取决于您想要如何构建它），那么这个问题是否注定会是 O(n!) ，因此是最好的通过决策算法（如 alpha/beta）解决，在限制允许采用的边总数的情况下，该算法会产生最佳结果？
Even if there were an example; you could probably normalize it to be all positive. Any actual representation of a negative weight is relative to some 0. I guess what I'm saying is that there probably isn't an application of negative weights that can't be done using exclusively positive weights.
EDIT: After thinking about this a little bit more, I suppose you could have situations where a given path has a negative weight. In this context; assuming the negative weight is bad,
you would have to have a situation where the only possible way to achieve the goal of getting to your desired endpoint, would mean there would have to be at least one point in your graph where you're REQUIRED to take the negative path (as in, no other option is available to reach your goal). But I suppose if the graph hasn't been traversed; how would you know it were true?EDIT (AGAIN): @Jim, I think you're right. The choke point isn't really relevant. I guess I was too quick to assume that it was because one question that pops into my mind when introducing negative edges is - if it is possible to traverse the graph without taking ANY negative edge, then what are the negative edges doing there in the first place? But, this doesn't hold very well, because - outside of hindsight - how would you ever know if a graph could or could not be traversed without going across a negative edge?
Also worth noting, according to the wikipedia page for Djikstra's algorithm :
So, even though this conversation is useful and thought provoking; maybe the title of the question should be "What is the proper algorithm to use for traversing a graph with negative edges?" Djikstra's algorithm was intended to find the shortest path. But, if you introduce positive and negative weights, then doesn't the goal change from finding the shortest path to finding the MOST positive - regardless of how many edges are on your chosen path? And if it does, what is your exit condition? The only way you could know you've reached the optimal solution would be if you happened across a path that included all positive edges without any negative edges - and wouldn't this scenario only occur by chance? So - if introducing a situation where there are positive and negative weights changes the goal to be the most positive (or negative depending on how you want to frame it) wouldn't this problem be doomed to O(n!) and therefor be best solved by a decision making algorithm (like alpha/beta) which would produce the best outcome given a restriction on the total amount of edges you're allowed to take?
如果您想找到游过水上乐园中一系列相连的水池的最快方法，并且它有水槽。
If you're trying to find the quickest way to swim across a series of linked pools in a water park, and it has flumes.