Finding the shortest path between two points is a fundamental problem in CS. Dijkstra's Algorithm is the "gold standard" for GPS routing, social networks, and data packet delivery.

Dijkstra's Live Sandbox

Click 'Play Dijkstra' to start from node A.

Unvisited

Current

Visited

Distance Records

Node A

Distance

Node B

∞

Distance

Node C

∞

Distance

Node D

∞

Distance

Node E

∞

Distance

Node F

∞

Distance

Algorithm Comparison

Dijkstra's

The fastest for non-negative weights. Used in nearly all map applications.

O(E log V)

Bellman-Ford

Slower than Dijkstra, but can handle negative edge weights. Detects negative cycles.

O(V * E)

Floyd-Warshall

Finds shortest paths between all pairs of nodes at once using Dynamic Programming.

O(V^3)

The Greedy Choice

Dijkstra is a Greedy Algorithm. At every step, it blindly trusts that the closest unvisited node is the best one to explore next.

Wait, Why No Negative Weights?

If a graph has negative edges, a "shorter" path could be found *after* a node is already marked as visited. Dijkstra's "greedy" logic doesn't allow it to go back and re-check, which leads to incorrect results.

Implementation

Pseudocode

1// Dijkstra's with Priority Queue
2function dijkstra(graph, start) {
3  const distances = {};
4  const pq = new MinPriorityQueue();
5 
6  for (let node in graph) {
7    distances[node] = Infinity;
8  }
9  distances[start] = 0;
10  pq.enqueue(start, 0);
11 
12  while (!pq.isEmpty()) {
13    const { element: u } = pq.dequeue();
14 
15    for (let v in graph[u]) {
16      const weight = graph[u][v];
17      const distance = distances[u] + weight;
18 
19      if (distance < distances[v]) {
20        distances[v] = distance;
21        pq.enqueue(v, distance);
22      }
23    }
24  }
25  return distances;
26}

Implementation

Pseudocode

1// Dijkstra's with Priority Queue
2function dijkstra(graph, start) {
3  const distances = {};
4  const pq = new MinPriorityQueue();
5 
6  for (let node in graph) {
7    distances[node] = Infinity;
8  }
9  distances[start] = 0;
10  pq.enqueue(start, 0);
11 
12  while (!pq.isEmpty()) {
13    const { element: u } = pq.dequeue();
14 
15    for (let v in graph[u]) {
16      const weight = graph[u][v];
17      const distance = distances[u] + weight;
18 
19      if (distance < distances[v]) {
20        distances[v] = distance;
21        pq.enqueue(v, distance);
22      }
23    }
24  }
25  return distances;
26}