Dijkstra: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 17: Line 17:
* weight function ''w'' : ''E'' → ℜ
* weight function ''w'' : ''E'' → ℜ
* ∀ (''u,v'') ∈ E : ''w''(''u,v'') ≥ 0
* ∀ (''u,v'') ∈ E : ''w''(''u,v'') ≥ 0
* source ''s'' : ''s'' &isin ''V''
* source ''s'' : ''s'' ∈ ''V''
* Datastruct ''S''  
* Datastruct ''S''  
* Datastruct ''Q''
* Datastruct ''Q''

Revision as of 16:57, 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 → ℜ
  • ∀ (u,v) ∈ E : w(u,v) ≥ 0
  • source s : sV
  • Datastruct S
  • Datastruct Q

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 vG.V
2         v.d = ∞
3         v.π = NIL
4 s.d = 0