Data Structures and Algorithms · Graphs

Dijkstra's algorithm

Finding the cheapest path from one vertex to all others when no edge weight is negative.

Also known as: single-source shortest path, non-negative weighted shortest path.

Start a lesson on Dijkstra's algorithm

Learn first

• Graph traversal (BFS and DFS): Visiting every reachable vertex, either level by level (BFS) or by diving deep first (DFS).
• Heaps and priority queues: A tree-shaped structure that always keeps the smallest, or largest, element quick to find.

Related topics

• Bellman-Ford algorithm: Finding shortest paths that still works when some edge weights are negative, at the cost of speed.