Content deleted Content added
→top: | Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget |
Restore indentation on pseudocode examples |
||
Line 39:
In the following [[pseudocode]], {{mono|dist}} is an array that contains the current distances from the {{mono|<var>source</var>}} to other vertices, i.e. {{mono|dist[<var>u</var>]}} is the current distance from the source to the vertex {{mono|<var>u</var>}}. The {{mono|prev}} array contains pointers to previous-hop nodes on the shortest path from source to the given vertex (equivalently, it is the ''next-hop'' on the path ''from'' the given vertex ''to'' the source). The code {{mono|u ← vertex in ''Q'' with min dist[u]}}, searches for the vertex {{mono|<var>u</var>}} in the vertex set {{mono|<var>Q</var>}} that has the least {{mono|dist[<var>u</var>]}} value. {{mono|Graph.Edges(<var>u</var>, <var>v</var>)}} returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes {{mono|<var>u</var>}} and {{mono|<var>v</var>}}. The variable {{mono|<var>alt</var>}} on line 14 is the length of the path from the {{mono|<var>source</var>}} node to the neighbor node {{mono|<var>v</var>}} if it were to go through {{mono|<var>u</var>}}. If this path is shorter than the current shortest path recorded for {{mono|<var>v</var>}}, then the distance of {{mono|<var>v</var>}} is updated to {{mono|<var>alt</var>}}.<ref name=" mehlhorn" />
[[File:DijkstraDemo.gif|thumb|A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting ''u'' and prev[''u'']. Blue lines indicate where relaxing happens, i.e., connecting ''v'' with a node ''u'' in ''Q'', which gives a shorter path from the source to ''v''.]]
1 '''function''' Dijkstra(''Graph'', ''source''):
2
3 '''for each''' vertex ''v'' in ''Graph.Vertices'': 4 dist[''v''] ← INFINITY
5 prev[''v''] ← UNDEFINED
6 add ''v'' to ''Q''
7 dist[''source''] ← 0
8
9 '''while''' ''Q'' is not empty:
10 ''u'' ← vertex in ''Q'' with minimum dist[u]
11 remove u from ''Q''
12
13 '''for each''' neighbor ''v'' of ''u'' still in ''Q'':
14 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
15 '''if''' ''alt'' < dist[''v'']:
16 dist[''v''] ← ''alt''
17 prev[''v''] ← ''u''
18
▲ 20 '''return''' dist[], prev[]
To find the shortest path between vertices {{mono|<var>source</var>}} and {{mono|<var>target</var>}}, the search terminates after line 10 if {{mono|<var>u</var> {{=}} <var>target</var>}}. The shortest path from {{mono|<var>source</var>}} to {{mono|<var>target</var>}} can be obtained by reverse iteration:
2 ''u'' ← ''target''
3 '''if''' prev[''u''] is defined '''or''' ''u'' = ''source'': ''// 4 '''while''' ''u'' is defined: ''// Construct the shortest path with a stack S''
5 insert ''u'' at the beginning of ''S'' ''// Push the vertex onto the stack''
6 ''u'' ← prev[''u''] ''// Traverse from target to source''
Now sequence {{mono|<var>S</var>}} is the list of vertices constituting one of the shortest paths from {{mono|<var>source</var>}} to {{mono|<var>target</var>}}, or the empty sequence if no path exists.
Line 72 ⟶ 75:
===Using a priority queue===
A min-priority queue is an abstract data type that provides 3 basic operations: {{mono|add_with_priority()}}, {{mono|decrease_priority()}} and {{mono|extract_min()}}. As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue. Notably, [[Fibonacci heap]]{{sfn|Fredman|Tarjan|1984}} or [[Brodal queue]] offer optimal implementations for those 3 operations. As the algorithm is slightly different in appearance, it is mentioned here, in pseudocode as well:
1 '''function''' Dijkstra(''Graph'', ''source''):
2 create vertex priority queue Q
3
4 dist[''source''] ← 0 ''// Initialization''
5 ''Q''.add_with_priority(''source'', 0) ''// associated priority equals dist[·]''
6
7 '''for each''' vertex ''v'' in ''Graph.Vertices'':
8 '''if''' ''v'' ≠ ''source''
9 prev[''v''] ← UNDEFINED ''// Predecessor of v''
10 dist[''v''] ← INFINITY ''// Unknown distance from source to v''
11 Q.add_with_priority(v, INFINITY)
12
13
14 '''while''' ''Q'' is not empty: ''// The main loop''
15 ''u'' ← ''Q''.extract_min() ''// Remove and return best vertex''
16 '''for each''' neighbor ''v'' of ''u'': ''// Go through all v neighbors of u''
17 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
18 '''if''' ''alt'' < dist[''v'']:
19 prev[''v''] ← ''u''
20 dist[''v''] ← ''alt''
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}}
Line 151 ⟶ 156:
Moreover, not inserting all nodes in a graph makes it possible to extend the algorithm to find the shortest path from a single source to the closest of a set of target nodes on infinite graphs or those too large to represent in memory. The resulting algorithm is called ''uniform-cost search'' (UCS) in the artificial intelligence literature{{r|felner}}<ref name="aima">{{Cite AIMA|3|pages=75, 81}}</ref><ref>Sometimes also ''least-cost-first search'': {{cite journal |last=Nau |first=Dana S. |year=1983 |title=Expert computer systems |url=https://www.cs.umd.edu/~nau/papers/nau1983expert.pdf |journal=Computer |publisher=IEEE |volume=16 |issue=2 |pages=63–85 |doi=10.1109/mc.1983.1654302 |s2cid=7301753}}</ref> and can be expressed in pseudocode as<!--NOTE TO EDITORS: Don't get confused by "uniform" in the name and remove costs from the pseudocode. UCS includes costs and is different from breadth-first search.-->
'''procedure''' uniform_cost_search(start) '''is'''
node ← start
frontier ← priority queue containing node only
expanded ← empty set
'''do'''
'''if''' frontier is empty '''then'''
'''return''' failure
node ← frontier.pop()
'''if''' node is a goal state '''then'''
'''return''' solution(node)
expanded.add(node)
'''for each''' of node's neighbors ''n'' '''do'''
'''if''' ''n'' is not in expanded and not in frontier '''then'''
frontier.add(''n'')
'''else if''' ''n'' is in frontier with higher cost
replace existing node with ''n''
Its complexity can be expressed in an alternative way for very large graphs: when {{math|''C''<sup>*</sup>}} is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least ''{{mvar|ε}}'', and the number of neighbors per node is bounded by ''{{mvar|b}}'', then the algorithm's worst-case time and space complexity are both in {{math|''O''(''b''<sup>1+⌊''C''<sup>*</sup> {{frac}} ''ε''⌋</sup>)}}.{{r|aima}}
| |||