Why is it mandatory that Dijkstra's algorithm extracts min in each round?

Question

Consider the graph is valid for applying Dijkstra's algorithm i.e. there are no negative edge weights. I'm having a difficult time convincing myself that Dijkstra's algorithm only works if the minimum distance node in each round is chosen to be extracted. What would constitute a proof that extracting anything but the minimum distance node would lead to failure of the Dijkstra's algorithm? I'm looking for a good argument but supporting examples are welcome.

Answer 1

If you extract a non-minimum node, then you will have extracted a node for which the shortest distance was not known at the time of extraction. It will be computed later, but the node will not be extracted again, so you will be left with at least one wrong minimum distance at the end.

Example:

You will have d[1] = 0, then you will extract this since it's the only one to extract.

This will set:

d[3] = 3
d[2] = 1

Now you should extract 2, but let's say you extract 3.

You will set d[4] = 4.

Now let's say you extract 2 and set d[3] = 2.

Next, only 4 is left to be extracted. You extract it and you're done.

You're left with a wrong value of d[4] = 4 instead of d[4] = 3.

Note that this assumes that you cannot extract a node multiple times (which you cannot in a classical Dijkstra's algorithm). If you allow for this, then what you suggest does work, but is arguably neither efficient nor Dijkstra's anymore.