מה הסיבה שאלגוריתם של דייקסטרה דורש פונקציית משקל אי שלילית?
Date: 08 Apr 2014 12:28
Number of posts: 2
RSS: New posts
Dijkstra's running time depends on the fact that once we finished looking at a vertex, we will never need to look at it again. If there were negative edges, after we finished with a vertex v at distance 10, we might find out later that its distance is actually 8, and that would mean we haven't finished with v.
Try to come up with an example (it's not too difficult) where Dijkstra doesn't work if there is a negative edge.