Codacoda
Back to Academy

graphs

Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach, always expanding the closest unvisited vertex. It is widely used in routing protocols and navigation systems.

Use Cases

  • •GPS navigation and shortest route finding
  • •Network routing protocols (OSPF)
  • •Finding shortest paths in games and simulations

Complexity Analysis

MetricBestAverageWorst
TimeO((V + E) log V)O((V + E) log V)O((V + E) log V)
SpaceO(V)

Visualization

4251810263ABCDEF
Speed:1x
Graph readyStep 1 / 12

Implementation

Output

Click "Run Code" to see output...