Skip to content
BENIBIX Learn

Dijkstra's Algorithm

Development🧮 Algorithms & Data StructuresSearch Algorithms

Also known as Dijkstra, Dijkstra Shortest Path, Shortest Path Algorithm

A way to find the shortest route through a graph where each road has a length.

Think of it like

Think of it like a map app. It tries the closest roads first and keeps the best time to each place.

Example

Lucy's delivery app finds the quickest route across 400 streets. Dijkstra's algorithm picks a path of 9 minutes over one of 14.

Why it matters

Route planners, network routers and games all find short paths with it or a close cousin.

Definition

Dijkstra's algorithm finds the shortest path from one node to every other node. It works on a graph whose edges have a length, or weight. It keeps a best-known distance for each node, starting from zero at the start. Each step, it takes the closest node it has not finished and checks its neighbours. A heap makes picking the closest node quick. It only works when no edge has a negative weight.

Common mistake

Using it on a graph with negative weights. It can give a wrong answer; other algorithms handle that case.

Key takeaways

  1. 1
    Shortest by weight. Not by number of steps.
  2. 2
    Closest first. A heap picks it fast.
  3. 3
    No negative weights. Or it goes wrong.