Dijkstra: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 8: | Line 8: | ||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/dijkstra-2310 Openlearnware]</div> | <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/dijkstra-2310 Openlearnware]</div> | ||
</div> | </div> | ||
''Dijstra's algorithm'' is a graph algortihm solving the single-source shortest-paths problem. | |||
Dijstra's algorithm is a graph algortihm solving the single-source shortest-paths problem. | |||
== Requirements == | == Requirements == | ||
| Line 20: | Line 16: | ||
* directed Grpah ''G'' = (''V,E'') | * directed Grpah ''G'' = (''V,E'') | ||
* weight function ''w'' : ''E'' → ℜ | * weight function ''w'' : ''E'' → ℜ | ||
* w(''u,v'') >= 0 ∀ (''u,v'') ∈ E | |||
Revision as of 16:37, 25 September 2014
Dijstra's algorithm is a graph algortihm solving the single-source shortest-paths problem.
Requirements
- directed Grpah G = (V,E)
- weight function w : E → ℜ
- w(u,v) >= 0 ∀ (u,v) ∈ E
Pseudocode
DIJKSTRA(G,w,s)
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)
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)
INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v ∈ G.V
2 v.d = ∞
3 v.π = NIL
4 s.d = 0