Negative weights using Dijkstra’s Algorithm

by

The algorithm you have suggested will indeed find the shortest path in this graph, but not all graphs in general. For example, consider this graph:

A directed graph with four nodes, A, B, C, and D. Node A has an edge to B of cost 1, an edge to C of cost 0, and an edge to D of cost 99. Node B has an edge to cost 1 to node C. Node D has an edge of cost -300 to node B.

Let’s trace through the execution of your algorithm.

  1. First, you set d(A) to 0 and the other distances to ∞.
  2. You then expand out node A, setting d(B) to 1, d(C) to 0, and d(D) to 99.
  3. Next, you expand out C, with no net changes.
  4. You then expand out B, which has no effect.
  5. Finally, you expand D, which changes d(B) to -201.

Notice that at the end of this, though, that d(C) is still 0, even though the shortest path to C has length -200. This means that your algorithm doesn’t compute the correct distances to all the nodes. Moreover, even if you were to store back pointers saying how to get from each node to the start node A, you’d end taking the wrong path back from C to A.

The reason for this is that Dijkstra’s algorithm (and your algorithm) are greedy algorithms that assume that once they’ve computed the distance to some node, the distance found must be the optimal distance. In other words, the algorithm doesn’t allow itself to take the distance of a node it has expanded and change what that distance is. In the case of negative edges, your algorithm, and Dijkstra’s algorithm, can be “surprised” by seeing a negative-cost edge that would indeed decrease the cost of the best path from the starting node to some other node.

Hope this helps!

More Related Contents:

  1. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  2. Why does Dijkstra’s algorithm use decrease-key?
  3. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  4. Finding all cycles in a directed graph
  5. Find the shortest path in a graph which visits certain nodes
  6. Finding all the shortest paths between two nodes in unweighted undirected graph
  7. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  8. How does Dijkstra’s Algorithm and A-Star compare?
  9. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  10. Find cycle of shortest length in a directed graph with positive weights
  11. graph – Dijkstra for The Single-Source Longest Path
  12. The best shortest path algorithm
  13. Why is depth-first search claimed to be space efficient?
  14. Shortest path to transform one word into another
  15. Algorithm to simplify a weighted directed graph of debts
  16. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  17. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  18. Quicksort: Choosing the pivot
  19. Breadth First Vs Depth First
  20. Is there an algorithm for color mixing that works like mixing real colors?
  21. Algorithm to list unique permutations of string with duplicate letters
  22. Collision detection of huge number of circles
  23. Compute rank of a combination?
  24. Efficiently selecting a set of random elements from a linked list
  25. Find if a point is inside a convex hull for a set of points without computing the hull itself
  26. Myers diff algorithm vs Hunt–McIlroy algorithm
  27. Given Prime Number N, Compute the Next Prime?
  28. Optimized low-accuracy approximation to `rootn(x, n)`
  29. What are probabilistic data structures?
  30. Connected Component Labeling – Implementation

Leave a Comment