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)$ , where $V$ is the set of vertices, $E$ is the set of edges, and a source node $s \in V$ .
• Output: The shortest path distances from $s$ to all other nodes in $V$ .

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:
   

   $$\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: $\text{dist}(s) = 0, \text{dist}(v) = \infty \, \text{for all} \, v \neq s$

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

• Relaxation Step: for each edge $(u, v)$ with weight $w(u, v)$ : If $\text{dist}(v) > \text{dist}(u) + w(u, v)$ , update:
  $$\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 )$ with the smallest tentative distance:
  $$u = \arg \min_{v \in Q} \text{dist}(v)$$

Why It Works: By processing the node with the smallest $\text{dist}(v)$ , we guarantee the shortest path from the source to $( 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) )$ , we assume the truth of $( P(1), P(2), \dots, P(k) )$ to prove $( P(k+1) )$ . This differs from regular induction, which assumes only $( P(k) )$ to prove $( 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 )$ is initialized with $\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 )$ is dequeued from the priority queue. Since $\text{dist}(u)$ is the smallest remaining distance, and all previous nodes have correct distances, $\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;
  }
}

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);

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);

Example Walkthrough

Graph Representation

• Nodes: $A, B, C, D$
• Edges:
  • $A \to B = (1), A \to C = (4)$
  • $B \to C = (2), B \to D = (5)$
  • $C \to D = (1)$

Step-by-Step Execution

1. Initialize distances:
   

   $$\text{dist}(A) = 0, \; \text{dist}(B) = \infty, \; \text{dist}(C) = \infty, \; \text{dist}(D) = \infty$$

2. Process A:

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

3. Process B:

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

4. Process C:

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

5. Process D:

   • No further updates.

Final Distances and Path

Optimizations and Time Complexity

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

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)$ 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:

• Dijkstra's Algorithm PDF
• Shortest Path Algorithms on SlideShare

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!