First time here? Checkout the FAQ!
0 votes
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
asked in Algorithms by Boss (6.1k points)   | 147 views

1 Answer

+3 votes
Why dijkastra provide wrong result for -ve edge. Because dijkastra supports increments of distance, when it goes from one vertex to other. In the middle if we get some -ve edge, this assumption will be violated. That is why dijkastra gives incorrect result for some cases.

Dijkastra doesnot check if there is a -ve edge or not. If it's assumtion is true, dijkastra even give correct result with -ve weight edges too.
answered by Veteran (58.7k points)  

Top Users Sep 2017
  1. Habibkhan

    8796 Points

  2. rishu_darkshadow

    3572 Points

  3. Warrior

    2914 Points

  4. Arjun

    2840 Points

  5. A_i_$_h

    2550 Points

  6. manu00x

    2268 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points

26,346 questions
33,927 answers
31,231 users