Dijkstra's Algorithm

graph

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Finds the shortest path between nodes in a weighted graph using a priority queue.

Time Complexity

Best

\mathrm{O}\left(V + E \log V\right)

Avg

\mathrm{O}\left(V + E \log V\right)

Worst

\mathrm{O}\left(V^{2}\right)

Space Complexity

Aux

\mathrm{O}\left(V\right)

Priority queue + dist[] array — O(V) nodes

Pseudocode

1procedure Dijkstra(graph, start, end)

2dist[start] = 0

3while PQ is not empty do

4u = PQ.extractMin()

5for each neighbor v of u do

6if dist[u]+w(u,v) < dist[v] then relax