Have Geek Brain

Proof that distance values ​​extracted in Dijkstra's algorithm don't decrease?

I go through my old algorithms and come across this proof. It was from an assignment I had and I got it right, but I feel like evidence is definitely lacking.

The question is prove that the distance values taken from the priority queue in Dijkstra algorithm is a non-decreasing sequence.

My proof looks like this:

Evidence. Fist, suppose we are pulling a vertex from Q with a d-value 'i'. Next time we are a vertex with a d-value 'j'. When we pulled i, we completed our d-value and calculated the shortest path from the starting vertex, s, to i. since we have positive edge weights, it is not possible for our d-values ​​to shrink as we add vertices to our path. If, after pulling i out of Q, we pull j with a smaller value of d, we may not have a shortest path to i, since we may be able to reach i via j. However, we have already calculated the shortest path to i. We have not tested the possible path. We no longer have a guaranteed path. Contradiction.

How can this evidence be improved? Or better yet, is there another approach? It just seems pretty weak :)

Edit: Sorry, in this case my priority queue is implemented with Min-heap

+2


a source to share


1 answer


Let them be set (they are all true, since this is basically the definition of an algorithm):

  • The priority queue in Dijkstra's algorithm will give you the node with the smallest d value at each iteration of the algorithm.
  • No negative edge weights.
  • Once the node object is removed, it will never be returned to the queue.
  • The d-value of a node that was canceled is final and will not change from that point on.


Continuing with (1), the d-value of that dequeued node, assuming (2), will be at least equal to the previous d-value extracted, since each node d value depends on the d-value of the nodes allocated before it, which is its own kind of recursive definition. Since (3) and (4) are correct, this recursive definition ends at the starting node, which has a d-value of 0.
So, if each node d-value is at least equal to the d-value before it, and (1) still applies, a non-decreasing set of d-values ​​retrieved from the priority queue .

(After reading this and what you wrote, it's basically the same, but presented a little better, I think)

+1


a source






More articles:


All Articles