CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
venkysmarty
venkysmarty

Reputation: 11431

Understanding this explanation on why Dijkstra's algorithm fails on graphs with negative edges?

I am reading about Shortest paths in the presence of negative edges in book titled algorithms by Sanjoy DasGupta (page 122)

http://beust.com/algorithms.pdf

Dijkstra's algorithm works in part because the shortest path from the starting point s to any node v must pass exclusively through nodes that are closer than v. This no longer holds when edge lengths can be negative. In Figure 4.12, the shortest path from S to A passes through B,a node that is further away.

    (S,A) = 3, (S,B)=4, (B,A)= =2



S-----3--------A
   |           ^
   |           |
   4          -2
   |           |
   |           |
   B----------->

What needs to be changed in order to accommodate this new complication? To answer this, let's take a particular high-level view of Dijkstra's algorithm. A crucial invariant is that the dist values it maintains are always either overestimates or exactly correct. They start off at infinity, and the only way they ever change is by updating along an edge

:

procedure update((u; v) belongsto E)
dist(v) = min{dist(v), dist(u) + l(u,v)}

This update operation is simply an expression of the fact that the distance to v cannot possibly be more than the distance to u, plus l(u, v). It has the following properties. 1. It gives the correct distance to v in the particular case where u is the second-last node in the shortest path to v, and dist(u) is correctly set. 2. It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt.

This operation is extremely useful: it is harmless, and if used carefully, will correctly set distances. In fact, Dijkstra's algorithm can be thought of simply as a sequence of update's. We know this particular sequence doesn't work with negative edges, but is there some other sequence that does? To get a sense of the properties this sequence must possess, let's pick a node t and look at the shortest path to it from s.

My questions on above text is

  1. What does author mean by second property? "It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt." I am not able to understand this
  2. What does author mean by "We know this particular sequence doesn't work with negative edges, but is there some other sequence that does?" I am not native english speaker so difficult in understanding this statement?

Upvotes: 0

Views: 1719

Answers (1)

templatetypedef
templatetypedef

Reputation: 372724

For your first question - what does the statement "it will never make dist(v) too small" mean? - I think the author is referring to a particular property of Dijkstra's algorithm: if you look at the distances that Dijkstra's algorithm stores to each node in the graph, the distance stored to a particular node is never less than the actual distance. In fact, if you have nonnegative edge weights and look at the distances as you run Dijkstra's algorithm, the distances will keep decreasing and decreasing until they eventually converge on the true distances. In that sense, Dijkstra's algorithm continuously gets better and better approximations of the true distance, but at no point ever has a distance to a node that's too short.

For your second question, I think the author is asking you to think about what would happen if you were to run Dijkstra's algorithm on any input graph. As the algorithm runs, it keeps making updates to its guesses of the distances between the start node and each other node in the graph. The author is saying that if you run Dijkstra's algorithm and watch how it works, what you'll see is a series of calls to some subroutine update that changes those distances. Even if the algorithm gives the wrong final answer, it still works by calling update repeatedly.

Upvotes: 1

Related Questions