即使在具有负边缘权重的图形中,我们是否可以使用Dijkstra来找到最短路径？

Question

假设我有一个图表,其中最小边缘权重是-100.我可以在所有边缘添加100作为偏移并使用Dijkstra的算法吗？

请帮我理解为什么这样的方法会给出错误的解决方案.

Answer 1

向每个边缘权重添加100会给出错误的解决方案,因为它会使具有更多边缘的路径比具有更少边缘的路径更糟糕.

例如,假设我们有一个图形,从A点到B点的最短路径有3条边和5条总距离.假设从A点到B点的其他路径有2条边但总距离为10条.

如果我们为每个边权重加100,那么第一条路径的成本为305,而第二条路径的成本为210.因此第二条路径比第一条路径短.

因此,我们可以得出结论,向每个边缘权重添加偏移或偏移不一定保留最短路径.