Dijkstra's algorithm: Difference between revisions

Revision as of 16:06, 11 May 2025

Revision as of 14:13, 14 May 2025

Line 50:

9 '''while''' ''Q'' is not empty:

10 ''u'' ← vertex in ''Q'' with minimum dist[u]

11 Q.remove (u from ''Q'')

12

13 '''for each''' neighborarc ''v'' of ''(u'', stillv) in ''Q'':

14 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')

15 '''if''' ''alt'' < dist[''v'']:

Line 66:

3 '''if''' prev[''u''] is defined '''or''' ''u'' = ''source'': ''// Proceed if the vertex is reachable''

4 '''while''' ''u'' is defined: ''// Construct the shortest path with a stack S''

5 insert ''S.push(u'') at the beginning of ''S'' ''// Push the vertex onto the stack''

6 ''u'' ← prev[''u''] ''// Traverse from target to source''

Line 77:

1 '''function''' Dijkstra(''Graph'', ''source''):

2 createQ vertex← priorityQueue queuestoring Qvertex priority

3

4 dist[''source''] ← 0 ''// Initialization''

5 ''Q''.add_with_priority(''source'', 0) ''// associated priority equals dist[·]''

Line 91:

14 '''while''' ''Q'' is not empty: ''// The main loop''

15 ''u'' ← ''Q''.extract_min() ''// Remove and return best vertex''

16 '''for each''' neighborarc (u, ''v'') of ''u'': ''// Go through all v neighbors of u''

17 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')

18 '''if''' ''alt'' < dist[''v'']:

Line 98:

21 ''Q''.decrease_priority(''v'', ''alt'')

22

23 '''return''' (dist, prev)

Instead of filling the priority queue with all nodes in the initialization phase, it is possible to initialize it to contain only ''source''; then, inside the <code>'''if''' ''alt'' < dist[''v'']</code> block, the {{mono|decrease_priority()}} becomes an {{mono|add_with_priority()}} operation.<ref name=" mehlhorn" />{{rp|198}}