graph - 具有一个负边缘的最短路径

Question

令 G(V,E) 是一个没有负环的有向连通图。除 ONE 边外，所有边都具有非负权重。从 s,t 在 V 中找到一条简单的最短路径。

我的想法 -

1. 在图上做一个 BFS，找到负权重的边。
2. 将此负权重添加到所有边缘，因此我们消除了负权重。
3. 做 Dijkstra 算法。

我的想法行不通。

你能帮我找出原因吗？

谢谢你。

标签： graphdijkstradirected-graph

Answer 1

您的方法不起作用的原因是它不公平地惩罚了具有更多边缘的路径。

想象一下从源节点到目的地的两条路径，一条边多但权重较低，另一条边少但权重较高。假设添加到每条边的权重为 3。

原始路径：

S -> 1 -> 1 -> 1 -> 1 -> 1 -> T    wt = 5
S -> 4 -> 3 -> T                   wt = 7

添加权重后的路径：

S -> 4 -> 4 -> 4 -> 4 -> 4 -> T    wt = 20
S -> 7 -> 6 -> T                   wt = 13

如您所见，第二条路径现在被错误地识别为较短的路径。