2
pq.insert(s, 0.0);
while (!pq.isEmpty()) {
  int v = pq.delMin();
  for (DirectedEdge e: G.adj(v))
    relax(e);
}

...  

void relax (DirectedEdge e) {
  int v = e.from(), w = e.to();
  if(distTo[w] > distTo[v] + e.weight()) {
    distTo[w] = distTo[v] + e.weight();
    edgeTo[w] = e;


    // once a node is newly relaxed, it is inserted to pq,
    // meaning that even if a node receives a negative (shorter)
    // path late, we won't miss its contribution; pq will still
    // dequeue it to relax its adjacent, am I correct?

    if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
    else pq.insert(w, distTo[w]);
  }
}

So why can Dijkstra's algorithm not handle negative-weight graph? If it's implemented in the above way that uses a pq to store the nodes that has distTo value change, is it actually the same as the SPFA algorithm except that SPFA algorithm may use FIFO queue instead of priority queue?

jack
  • 1,787
  • 14
  • 30
  • Sorry this was closed. I don't think it's a duplicate of the linked question. – Mark Jul 07 '18 at 21:04
  • Thanks. It is indeed not a duplicate. I wanted to ask if this version of implementation of Dijkstra can solve negative weight or not, and also if it's the same as SPFA. – jack Jul 08 '18 at 05:47
  • I wish I had more space, but I think you will find graphs where this algorithm is significantly less efficient than Dijksta, because negative weights can cause the same node's edges to be relaxed more than once. – Mark Jul 08 '18 at 05:51
  • Hello all, i am sorry that i have to say this question is not a duplicate, because indeed i found that [priority queue based Dijkstra](https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DijkstraSP.java.html) can solve negative weight graph. It means that the one i mentioned here is not the original version of Dijkstra. The original one indeed cannot solve negative weight, but pq based one can. That's the answer I found, not sure if it's correct. Also pq based Dijkstra is not SPFA, but similar. SPFA is FIFO and performance can be better typically though worst case is also n^2. – jack Jul 08 '18 at 19:41
  • the link you posted has: "@throws IllegalArgumentException if an edge weight is negative" – Mark Jul 08 '18 at 19:44
  • I think that is to avoid n^2 scenario. If you remove that exception, it still works. – jack Jul 09 '18 at 06:07

0 Answers0