DEV Community

Cover image for Understanding Dijkstra's Algorithm: From Theory to Implementation
Piyush Chauhan
Piyush Chauhan

Posted on

Understanding Dijkstra's Algorithm: From Theory to Implementation

Dijkstra's algorithm is a classic pathfinding algorithm used in graph theory to find the shortest path from a source node to all other nodes in a graph. In this article, we’ll explore the algorithm, its proof of correctness, and provide an implementation in JavaScript.

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a greedy algorithm designed to find the shortest paths from a single source node in a weighted graph with non-negative edge weights. It was proposed by Edsger W. Dijkstra in 1956 and remains one of the most widely used algorithms in computer science.

Input and Output

  • Input: A graph G=(V,E)G = (V, E) , where VV is the set of vertices, EE is the set of edges, and a source node sVs \in V .
  • Output: The shortest path distances from ss to all other nodes in VV .

Core Concepts

  1. Relaxation: The process of updating the shortest known distance to a node.
  2. Priority Queue: Efficiently fetches the node with the smallest tentative distance.
  3. Greedy Approach: Processes nodes in non-decreasing order of their shortest distances.

The Algorithm

  1. Initialize distances:

    dist(s)=0,dist(v)=  vs \text{dist}(s) = 0, \text{dist}(v) = \infty \; \quad \forall v \neq s
  2. Use a priority queue to store nodes based on their distances.

  3. Repeatedly extract the node with the smallest distance and relax its neighbors.


Relaxation - Mathematical Explanation

  • Initialization: dist(s)=0,dist(v)=for allvs\text{dist}(s) = 0, \text{dist}(v) = \infty \, \text{for all} \, v \neq s

where (s)( s ) is the source node, and (v)( v ) represents any other node.

  • Relaxation Step: for each edge (u,v)(u, v) with weight w(u,v)w(u, v) : If dist(v)>dist(u)+w(u,v)\text{dist}(v) > \text{dist}(u) + w(u, v) , update:
    dist(v)=dist(u)+w(u,v),prev(v)=u\text{dist}(v) = \text{dist}(u) + w(u, v), \quad \text{prev}(v) = u

Why It Works: Relaxation ensures that we always find the shortest path to a node by progressively updating the distance when a shorter path is found.


Priority Queue - Mathematical Explanation

  • Queue Operation: The priority queue always dequeues the node (u)( u ) with the smallest tentative distance:
    u=argminvQdist(v)u = \arg \min_{v \in Q} \text{dist}(v)

Why It Works: By processing the node with the smallest dist(v)\text{dist}(v) , we guarantee the shortest path from the source to (u)( u ) .


Proof of Correctness

We prove the correctness of Dijkstra’s algorithm using strong induction.

What is Strong Induction?

Strong induction is a variant of mathematical induction where, to prove a statement (P(n))( P(n) ) , we assume the truth of (P(1),P(2),,P(k))( P(1), P(2), \dots, P(k) ) to prove (P(k+1))( P(k+1) ) . This differs from regular induction, which assumes only (P(k))( P(k) ) to prove (P(k+1))( P(k+1) ) . Explore it in greater detail in my other post.

Correctness of Dijkstra's Algorithm (Inductive Proof)

  1. Base Case:

    The source node (s)( s ) is initialized with dist(s)=0\text{dist}(s) = 0 , which is correct.

  2. Inductive Hypothesis:

    Assume all nodes processed so far have the correct shortest path distances.

  3. Inductive Step:

    The next node (u)( u ) is dequeued from the priority queue. Since dist(u)\text{dist}(u) is the smallest remaining distance, and all previous nodes have correct distances, dist(u)\text{dist}(u) is also correct.


JavaScript Implementation

Prerequisites (Priority Queue):

// Simplified Queue using Sorting
// Use Binary Heap (good)
// or  Binomial Heap (better) or Pairing Heap (best) 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(node, priority) {
    this.queue.push({ node, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}
Enter fullscreen mode Exit fullscreen mode

Here’s a JavaScript implementation of Dijkstra’s algorithm using a priority queue:

function dijkstra(graph, start) {
  const distances = {}; // Hold the shortest distance from the start node to all other nodes
  const previous = {}; // Stores the previous node for each node in the shortest path (used to reconstruct the path later).
  const pq = new PriorityQueue(); // Used to efficiently retrieve the node with the smallest tentative distance.

  // Initialize distances and previous
  for (let node in graph) {
    distances[node] = Infinity; // Start with infinite distances
    previous[node] = null; // No previous nodes at the start
  }
  distances[start] = 0; // Distance to the start node is 0

  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { node } = pq.dequeue(); // Get the node with the smallest tentative distance

    for (let neighbor in graph[node]) {
      const distance = graph[node][neighbor]; // The edge weight

      // Relaxation Step
      const newDist = distances[node] + distance;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist; // Update the shortest distance to the neighbor
        previous[neighbor] = node; // Update the previous node
        pq.enqueue(neighbor, newDist); // Enqueue the neighbor with the updated distance
      }
    }
  }

  return { distances, previous };
}

// Example usage
const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 }
};

const result = dijkstra(graph, 'A'); // Start node 'A'
console.log(result);
Enter fullscreen mode Exit fullscreen mode

Reconstruct Path

function reconstructPath(previous, start, end) {
  let path = [];
  let currentNode = end;
  while (currentNode !== start) {
    path.push(currentNode);
    currentNode = previous[currentNode];
  }
  path.push(start);
  return path.reverse(); // Reverse the path to get the correct order
}

// Example usage:
const path = reconstructPath(previous, startNode, "D");
console.log("Shortest path from A to D:", path);
Enter fullscreen mode Exit fullscreen mode

Example Walkthrough

Graph Representation

  • Nodes: A,B,C,DA, B, C, D
  • Edges:
    • AB=(1),AC=(4)A \to B = (1), A \to C = (4)
    • BC=(2),BD=(5)B \to C = (2), B \to D = (5)
    • CD=(1)C \to D = (1)

Step-by-Step Execution

  1. Initialize distances:

    dist(A)=0,  dist(B)=,  dist(C)=,  dist(D)= \text{dist}(A) = 0, \; \text{dist}(B) = \infty, \; \text{dist}(C) = \infty, \; \text{dist}(D) = \infty
  2. Process A:

    • Relax edges: AB,AC.A \to B, A \to C.
      dist(B)=1,  dist(C)=4\text{dist}(B) = 1, \; \text{dist}(C) = 4
  3. Process B:

    • Relax edges: BC,BD.B \to C, B \to D.
      dist(C)=3,  dist(D)=6\text{dist}(C) = 3, \; \text{dist}(D) = 6
  4. Process C:

    • Relax edge: CD.C \to D.
      dist(D)=4\text{dist}(D) = 4
  5. Process D:

    • No further updates.

Final Distances and Path

dist(A)=0,  dist(B)=1,  dist(C)=3,  dist(D)=4 \text{dist}(A) = 0, \; \text{dist}(B) = 1, \; \text{dist}(C) = 3, \; \text{dist}(D) = 4

ABCD A \to B \to C \to D

Optimizations and Time Complexity

Comparing the time complexities of Dijkstra's algorithm with different priority queue implementations:

Priority Queue Type Insert (M) Extract Min Decrease Key Overall Time Complexity
Simple Array O(1) O(V) O(V) O(V^2)
Binary Heap O(log V) O(log V) O(log V) O((V + E) log V)
Binomial Heap O(log V) O(log V) O(log V) O((V + E) log V)
Fibonacci Heap O(1) O(log V) O(1) O(V log V + E)
Pairing Heap O(1) O(log V) O(log V) O(V log V + E) (practical)

Key Points:

  1. Simple Array:
    • Inefficient for large graphs due to linear search for extract-min.
  2. Binary Heap:
    • Standard and commonly used due to its balance of simplicity and efficiency.
  3. Binomial Heap:
    • Slightly better theoretical guarantees but more complex to implement.
  4. Fibonacci Heap:
    • Best theoretical performance with O(1)O(1) amortized decrease-key, but harder to implement.
  5. Pairing Heap:
    • Simple and performs close to Fibonacci heap in practice.

Conclusion

Dijkstra’s algorithm is a powerful and efficient method for finding shortest paths in graphs with non-negative weights. While it has limitations (e.g., cannot handle negative edge weights), it’s widely used in networking, routing, and other applications.

  • Relaxation ensures shortest distances by iteratively updating paths.
  • Priority Queue guarantees we always process the closest node, maintaining correctness.
  • Correctness is proven via induction: Once a node's distance is finalized, it's guaranteed to be the shortest path.

Here are some detailed resources where you can explore Dijkstra's algorithm along with rigorous proofs and examples:

Additionally, Wikipedia offers a great overview of the topic.

Citations:
[1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf

Feel free to share your thoughts or improvements in the comments!

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Visualizing Promises and Async/Await 🤓

async await

☝️ Check out this all-time classic DEV post on visualizing Promises and Async/Await 🤓

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay