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


consider graph valid applying dijkstra's algorithm i.e. there no negative edge weights. i'm having difficult time convincing myself dijkstra's algorithm works if minimum distance node in each round chosen extracted. constitute proof extracting minimum distance node lead failure of dijkstra's algorithm? i'm looking argument supporting examples welcome.

if extract non-minimum node, have extracted node shortest distance not known @ time of extraction. computed later, node not extracted again, left @ least 1 wrong minimum distance @ end.

example:

enter image description here

you have d[1] = 0, extract since it's 1 extract.

this set:

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

now should extract 2, let's extract 3.

you set d[4] = 4.

now let's extract 2 , set d[3] = 2.

next, 4 left extracted. extract , you're done.

you're left wrong value of d[4] = 4 instead of d[4] = 3.

note assumes cannot extract node multiple times (which cannot in classical dijkstra's algorithm). if allow this, suggest work, arguably neither efficient nor dijkstra's anymore.


Comments