Algorithms/Graph/Dijkstra's Shortest Path

Dijkstra's Shortest Path

Find the shortest paths from a source node to all other nodes in a weighted graph.

GraphGreedyShortest PathO((V+E) log V)

Graph Visualization

A → G

1 / 0

Speed

dijkstra.js

1class PriorityQueue {

2 constructor() {

3 this.heap = [];

4 }

5 enqueue(node, priority) {

6 this.heap.push({ node, priority });

7 this.heap.sort((a, b) => a.priority - b.priority);

8 }

9 dequeue() {

10 return this.heap.shift().node;

11 }

12 isEmpty() {

13 return this.heap.length === 0;

14 }

15}

17function dijkstra(graph, source) {

18 const dist = {}; // dist from source to node

19 const prev = {}; // previous node in path

20 const visited = new Set();

21 const pq = new PriorityQueue();

23 // Initialize all distances to Infinity

24 for (const node in graph) {

25 dist[node] = Infinity;

26 prev[node] = null;

27 }

28 dist[source] = 0;

29 pq.enqueue(source, 0);

31 while (!pq.isEmpty()) {

32 const current = pq.dequeue();

33 if (visited.has(current)) continue;

34 visited.add(current);

36 // Explore each neighbor

37 for (const { node: nbr, weight } of graph[current]) {

38 if (visited.has(nbr)) continue;

39 const newDist = dist[current] + weight;

41 if (newDist < dist[nbr]) { // Relaxation

42 dist[nbr] = newDist;

43 prev[nbr] = current;

44 pq.enqueue(nbr, newDist);

45 }

46 }

47 }

49 return { dist, prev };

50}

52// Reconstruct the shortest path

53function getPath(prev, source, target) {

54 const path = [];

55 let curr = target;

56 while (curr !== null) {

57 path.unshift(curr);

58 curr = prev[curr];

59 }

60 return path;

61}

Algorithm Explanation

Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959, finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.

⚙️ How It Works

Initialize — Set the source node distance to 0 and all others to ∞. Add all nodes to a priority queue.
Extract Minimum — Dequeue the node with the smallest known distance.
Relax Edges — For each unvisited neighbor, check if going through the current node offers a shorter path. Update if it does.
Repeat — Continue until the priority queue is empty or the target node is reached.
Reconstruct — Follow the prev pointers backward from target to source.

🔑 Key Insight — Edge Relaxation

The core operation is relaxation: for a neighbor v of the current node u, if dist[u] + weight(u,v) < dist[v], update dist[v] and record prev[v] = u. Dijkstra's greedy approach guarantees that once a node is dequeued, its distance is final.

⚠️ Limitation: Dijkstra's algorithm does not work with negative edge weights. For graphs with negative weights, use the Bellman-Ford algorithm instead.

Click nodes to set source/target · Drag nodes to rearrange layout · Use controls to step through