Dijkstra: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 17: | Line 17: | ||
<code> | <code> | ||
DIJKSTRA(G,w,s) | DIJKSTRA(''G,w,s'') | ||
INITIALIZE-SINGLE-SOURCE(G,s) | 1 INITIALIZE-SINGLE-SOURCE(''G,s'') | ||
2 ''S'' = ∅ | |||
3 ''Q'' = ''G.V'' | |||
4 '''while''' ''Q'' ≠ ∅ | |||
5 ''u'' = EXTRACT-MIN(''Q'') | |||
6 ''S'' = ''S'' ∪ {''u''} | |||
7 '''for''' each vertex ''v'' ∈ G.''Adj''[''u''] | |||
8 RELAX(''u,v,w'') | |||
</code> | </code> | ||
< | <code> | ||
RELAX(''u,v,w'') | |||
1 '''if''' ''v.d'' > ''u.d'' + ''w''(''u,v'') | |||
2 ''v.d'' = ''u.d'' + ''w''(''u,v'') | |||
3 ''v.π'' = ''u'' | |||
</code> | |||
<code> | |||
INITIALIZE-SINGLE-SOURCE(''G,s'') | |||
1 '''for''' each vertex ''v'' ∈ ''G.V'' | |||
</ | 2 ''v.d'' = ∞ | ||
3 ''v.π'' = NIL | |||
4 ''s.d'' = 0 | |||
</code> | |||
Revision as of 15:59, 25 September 2014
Das is de Disjkstra
dhg
Pseudocode
DIJKSTRA(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S = ∅
3 Q = G.V
4 while Q ≠ ∅
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for each vertex v ∈ G.Adj[u]
8 RELAX(u,v,w)
RELAX(u,v,w)
1 if v.d > u.d + w(u,v)
2 v.d = u.d + w(u,v)
3 v.π = u
INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v ∈ G.V
2 v.d = ∞
3 v.π = NIL
4 s.d = 0