Dijkstra's Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
= Implementation = | = Implementation = | ||
<pre> | |||
Dijkstra(G, w, s) { | |||
// initialize | |||
for all v in V: | |||
d[v] = infty | |||
pi[v] = null | |||
d[s] = 0 | |||
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> | |||
Revision as of 01:11, 8 March 2024
Implementation
Dijkstra(G, w, s) {
// initialize
for all v in V:
d[v] = infty
pi[v] = null
d[s] = 0
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
