Counter example (graph with negative weight) for Dijkstra algorithm with binary heap

Question

I am wondering if someone can give a counter example (a directed graph with negative weights) that will not work for the following code (Dijkstra algorithm with Binary heap). I have tried a couple example but seem to work properly with negative edges that whenever we have better way to a certain node, it will update all its adjacent node's distance. Here are the examples

(0) ----2----> (3) -----1-----> (4)
 |              ^
 4              |
 |             -9
 v              |  
(1) ----6----> (2)               

it will print out => 0, 4, 10, 1, 2

and also

(0) ---1---> (1) ---1---> (2)
 |                         ^
 |                         |
100                      -5000
 |                         |
 \---------> (3) ----------/

this will print => 0, 1, -4900, 100

The following is the code in Java

public static void dijkstra(DirectedGraph G, int source) {
    int[] distTo = new int[G.V()];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    distTo[source] = 0;
    PriorityQueue<Node> pq = new PriorityQueue<Node>();
    pq.add(new Node(source, 0));

    while (!pq.isEmpty()) {
        Vertex vertex = pq.poll();
        for (WeightedEdge edge : G.adjTo(vertex.node)) {
            if (edge.weight + distTo[edge.from] < distTo[edge.to]) {
                 distTo[edge.to] = distTo[edge.from] + edge.weight;
                 Vertex adjNode = new Vertex(edge.to, distTo[edge.to]);
                 if (pq.contains(adjNode))
                      pq.remove(adjNode);
                 pq.add(adjNode);
            }
        }
    }
    for (int dist : distTo)
        System.out.print(dist + " ");
}

static class Vertex implements Comparable<Vertex> {
      int node;
      int weight;

      public Vertex(int node, int weight){
             this.node = node;
             this.weight = weight;
      }

      @Override
      public int compareTo(Vertex other) {
             return weight - other.weight;
      }

}

public class DirectedGraph {
       private final int V;
       private int[][]   G;

       public int V() {
              return V;
       }

       public DirectedGraph(int V) {
              this.V = V;
              G = new int[V][V];
       }

       public void addEdge(int v, int w, int weight) {
              G[v][w] = weight;
       }

       public List<WeightedEdge> adjTo(int v) {
              List<WeightedEdge> edges = new LinkedList<WeightedEdge>();
              for (int i = 0; i < V; i++)
                  if (G[v][i] != 0)
                     edges.add(new Edge(v, i, G[v][i]));
              return edges;
       }

}

[Check this Answer](http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) — gtgaxiola, May 28 '15 at 16:00
@gtgaxiola I actually tried one of the example from the answer, and it works with negative with my code — peter, May 28 '15 at 16:02

score 1 · Answer 1 · answered May 28 '15 at 16:10

1

In Dijkstra you are supposed to maintain a list of visited nodes. Once you expand a node, you know you already computed the best way to reach the node from the root, and you are not going to push this node again to the queue.

This is the nature of Dijkstra. If you don't maintain that list, your code will fall into infinite loop on negative loops. You can use Bellman-ford algorithm to compute single-source shortest path and detect negative loops if any.

answered May 28 '15 at 16:10

Aᴍɪʀ

7,623
3
38
52

that makes sense...but still wondering would this code that I have work for negative weight but not negative cycle ? – peter May 28 '15 at 22:03

Counter example (graph with negative weight) for Dijkstra algorithm with binary heap

1 Answers1