CODEWITHSUNDEEP
algorithmlanguage-agnosticcomputer-sciencedijkstra
fdh
fdh

Reputation: 5354

Why does Dijkstra's algorithm need to use the deleteMin() and decreaseKey()?

In most pieces of pseudocode, I usually find the following:

  • DeleteMin (Return the element with the smallest key and delete it from the set.)

  • DecreaseKey (Accomodate the decrease in key value of a particular element)

Upvotes: 2

Views: 1248

Answers (1)

amit
amit

Reputation: 178491

Why is DeleteMin being used to retrieve the smallest element- why not a random one?

We retrieve and delete the min elements from Q the set of open vertices because it ensures minimality (later used in the proof). Without it - the minimality feature is not guaranteed, and the solution will not be optimal (won't be the shortest path). Remember that once we found a path to v, we remove it from Q, and will never re-open it, so the edge we take out must have the one with the smallest path available.

Note that for this (the minimal) vertex, let it be v: for each u in Q d(u) + x <= d(v) - since dijkstra's algorithm is used when there are no negative edges, x >=0.
For any other vertex - which is not minimal - we cannot guarantee that there is no shorter path yet to be discovered.

What is the purpose of DecreaseKey? In pseudocode it's always called after the value of an element is changed. What is it doing?

The decrease is used because we might have found a new, better path to vertices that are connected to the last vertex we found. This step is the relaxation step dijkstra's algorithm is making. Remember that dijkstra's algorithm is always maintaining the shortest path found so far to each vertex, since the last step might have found a new shortest path to some vertex - this step is updating the shortest path found so far.

Upvotes: 5

Related Questions