# Dijkstra's Algorithm
- Requires non-negative weights.
- Uses [[priority-queue|min-priority queue]] to keep track of next vertices to
consider.
- Always chooses the "lights" or "closes" vertex in $Q$ to insert into $S$,
hence a [[greedy]] algorithm.
- If the min-priority queue is implemented by
- An array, $O(V^2)$
- A binary [[heap]], $O((V + E)\lg V)$
- A [[fibonacci-heap|Fibonacci heap]], $O(V\lg V + E)$
```
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = {}
Q = {}
for each vertex u in G.V
INSERT(Q, u)
while Q != {}
u = EXTRACT-MIN(Q)
S = S + {u}
for each vertex v in G.Adj[u]
RELAX(u, v, w)
if the call of RELAX decreased v.d
DECREASE-KEY(Q, v, v.d)
```