0
$\begingroup$

Can we store a struct in place of vertex. struct { int v, update_count; }

run dijkstra's algorithm and whenever a node is updated we will increase update_count value. If update_count value is greater than V(no of nodes) we will know that there is negative weight cycle. Is this a viable solution.

$\endgroup$
  • 1
    $\begingroup$ What is your question? $\endgroup$ – lox Jul 7 '19 at 18:42
2
$\begingroup$

No. In a graph with $n$ nodes, Dijkstra's algorithm never updates a node more than $n-1$ times, so your test will never change anything. More fundamentally, negative-weight edges or cycles don't cause Dijkstra to get into infinite loops; they just make it give wrong answers in some cases.

This answer on Stack Overflow gives more detail.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.