Why is it necessary for Dijkstra's algorithm to extract mines in every round?
We assume that the graph is valid for applying Dijkstra's algorithm, i.e. no negative rib weights. It's hard for me to convince myself that Dijkstra's algorithm only works if the minimum node distance is chosen in each round. What will serve as proof that extracting anything other than the minimum node distance will cause Dijkstra's algorithm to fail? I'm looking for a good argument, but support for examples is appreciated.
source to share
If you extract a non-minimum node, then you will extract the 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 retrieved again, so you leave at least one wrong minimum distance in the end.
Example:
You will have d[1] = 0
, then you will retrieve it as it will be the only one to be retrieved.
This will install:
d[3] = 3
d[2] = 1
You should now extract 2
, but say what you are retrieving 3
.
You install d[4] = 4
.
Now let's say that you are fetching 2
and installing d[3] = 2
.
Further, only remains 4
. You extract it and you're done.
You left the wrong value d[4] = 4
instead of d[4] = 3
.
Note that this assumes that you cannot extract a node multiple times (which is not possible in the classic Dijkstra algorithm). If you allow it, then what you are proposing works, but is possibly neither effective nor Dijkstra.
source to share