Dijkstra's Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
|||
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[ | {{Infobox Algorithm|runtime=O(VE) or O(V^2) depending on data structure|class=[[Graph Algorithm]], [[Greedy Algorithm]]}} | ||
'''Dijkstra's algorithm''' is a solution to the [[Shortest Path Problem|shortest path problem]] for graphs with positively-weighted edges. | |||
= Approach: Greedy = | |||
Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.'' | |||
To reach the shortest path, Dijkstra always picks the shortest edge | |||
leaving the known nodes. In each iteration, it finalizes the distance to | |||
a node by picking the shortest one. | |||
= Implementation = | = Implementation = | ||
<pre> | |||
Dijkstra(G, w, s) { | |||
// initialize | |||
for all v in V: | |||
d[v] = infty | |||
pi[v] = null | |||
d[s] = 0 | |||
Q = V // priority queue of nodes | |||
while Q is not empty: | |||
u = Q.extractMin() | |||
for all v in adj[u]: | |||
if d[v] > d[u] + w(u,v): | |||
d[v] = d[u] + w(u,v) | |||
pi[v] = u | |||
</pre> | |||
[[Category:Algorithms]] |
Latest revision as of 05:22, 20 March 2024
Dijkstra's algorithm is a solution to the shortest path problem for graphs with positively-weighted edges.
Approach: Greedy
Dijkstra's algorithm centers around this property: of all the edges leaving the source, the shortest edge must be in the shortest path.
To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes. In each iteration, it finalizes the distance to a node by picking the shortest one.
Implementation
Dijkstra(G, w, s) { // initialize for all v in V: d[v] = infty pi[v] = null d[s] = 0 Q = V // priority queue of nodes while Q is not empty: u = Q.extractMin() for all v in adj[u]: if d[v] > d[u] + w(u,v): d[v] = d[u] + w(u,v) pi[v] = u