具有一个负边的最短路径

Question

Let G(V,E) be a directed connected graph with no negative cycles in it. All the edges have non-negative weight, except ONE edge. Find a simple shortest path from s,t in V.

我的想法 -

对图做BFS，找到权重为负的边
将这个负权重添加到所有边上，所以我们消除了负权重。
做Dijkstra算法。

我的想法行不通。

你能帮我找出原因吗？

谢谢。

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

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

Answer 2

您的方法的问题在于，如果一个负边具有较大的负值，它可能会产生更多的负边。

你可以看看Bellman-Ford最短路径算法来解决这个问题：

1) 第一步是将源点到所有顶点的距离初始化为无穷大，到源点本身的距离初始化为0。创建一个大小为|V|的数组dist[]。除了 dist[src] 之外的所有值都是无限的，其中 src 是源顶点。

2) 这一步计算最短距离。执行 |V|-1 次，其中 |V|是给定图中的顶点数。 …..a) 对每条边 u-v 执行以下操作 ………………如果dist[v] > dist[u] + 边uv的权重，则更新dist[v] …………………….dist[v] = dist[u] + 边的权重uv

3) 此步骤报告图中是否存在负权重循环。对每条边 u-v 执行以下操作 ……如果dist[v] > dist[u] + 边uv的权重，则“Graph contains negative weight cycle” 步骤 3 的想法是，如果图形不包含负权重循环，步骤 2 保证最短距离。如果我们再次遍历所有边并为任何顶点获得更短的路径，则存在负权重循环

具有一个负边的最短路径

Shortest Paths with One negative edge

graph

directed-graph

dijkstra