即使在具有负边权重的图中，我们也可以使用 Dijkstra 来找到最短路径吗？
假设我有一个图，其中最小边权重为 -100。我可以将 100 作为所有边的偏移量并使用 Dijkstra 算法吗？
请帮助我理解为什么这种方法会给出错误的解决方案。
Suppose I have a graph where the minimum edge weight is −100. Can I add 100 as an offset to all the edges and use Dijkstra's algorithm?
Please help me understand why such a method gives wrong solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对每个边权重添加 100 会给出错误的解决方案，因为它会惩罚具有较多边的路径而不是具有较少边的路径。
例如，假设我们有一个图，从 A 点到 B 点的最短路径有 3 条边，总距离为 5。假设从 A 点到 B 点的其他路径有 2 条边，但总距离为 10。
如果我们将每个边权重加 100，则第一条路径的成本为 305，而第二条路径的成本为 210。因此第二条路径变得比第一条路径短。
因此，我们可以得出结论，为每个边权重添加偏移量或偏差并不一定能保留最短路径。
Adding 100 to every edge weight gives the wrong solution because it penalizes paths that have more edges than paths that have fewer edges.
For example, suppose we have a graph, and the shortest path from point A to point B has 3 edges and a total distance 5. Suppose some other path from point A to point B has 2 edges but a total distance of 10.
If we add 100 to each edge weight, then the first path has a cost of 305, while the second path has a cost of 210. So the second path becomes shorter than the first path.
Therefore, we can conclude that adding an offset or bias to each edge weight does not necessarily preserve shortest paths.