CODEWITHSUNDEEP
graphdijkstradirected-graph
Assaf
Assaf

Reputation: 1124

Shortest Paths with One negative edge

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.

My idea -

  1. Do a BFS on the graph, find the edge with the negative weight.
  2. Add this negative weight to all the edges, so we eliminate the negative weight.
  3. Do Dijkstra algorithm.

My idea doesn't work.

Can you please help me find out why?

Thank you.

Upvotes: 0

Views: 1074

Answers (2)

Yuxuan Jiang
Yuxuan Jiang

Reputation: 11

The problem with your approach is that it may create more negative edges if the one negative edge has a large negative value.

You can look into Bellman-Ford shortest path algorithm to solve this problem:

1) The first step is to initialize distances from source to all vertices as infinite and distance to source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.

2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph. …..a) Do following for each edge u-v ………………If dist[v] > dist[u] + weight of edge uv, then update dist[v] ………………….dist[v] = dist[u] + weight of edge uv

3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-v ……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle” The idea of step 3 is, step 2 guarantees shortest distances if graph doesn’t contain negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle

Upvotes: 0

beaker
beaker

Reputation: 16791

The reason that your approach doesn't work is that it unfairly penalizes paths with more edges.

Imagine two paths from a source node to a destination, one with more edges, but lower weight, and another with a fewer edges with higher weight. Let's assume that the weight added to each edge is 3.

Original paths:

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

Paths after adding weight:

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

As you can see, the second path is now incorrectly identified as the shorter one.

Upvotes: 2

Related Questions