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 $V$V is the set of vertices, $E$E is the set of edges, and a source node $s\in V$s∈V .
• Output: The shortest path distances from $s$s to all other nodes in $V$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)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }s$$dist(s)=0,dist(v)=∞∀v=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)=\mathrm{\infty }\text{for all}v\mathrm{\ne }s$dist(s)=0,dist(v)=∞for allv=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 $\text{dist}(v)>\text{dist}(u)w(u,v)$dist(v)>dist(u) w(u,v) , update:
  $$\text{dist}(v)=\text{dist}(u)w(u,v),\text{prev}(v)=u$$dist(v)=dist(u) w(u,v),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=\arg \underset{v\in Q}{\min }\text{dist}(v)$$u=argv∈Qmin​dist(v)
  • Why It Works: By processing the node with the smallest $(\text{dist}(v))$(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),\dots ,P(k))$(P(1),P(2),…,P(k)) to prove $(P(k1))$(P(k 1)) . This differs from regular induction, which assumes only $(P(k))$(P(k)) to prove $(P(k1))$(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 $\text{dist}(s)=0$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 $\text{dist}(u)$dist(u) is the smallest remaining distance, and all previous nodes have correct distances, $\text{dist}(u)$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
      const newDist = distances[node] + distance;

      // Relaxation Step
      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

// 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;
  }
}

Example Walkthrough

Graph Representation

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

Step-by-Step Execution

1. Initialize distances:
   

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

2. Process A:

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

3. Process B:

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

4. Process C:

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

5. Process D:

   • No further updates.

Final Distances and Path

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

$$A\to B\to C\to D$$A→B→C→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) ) 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!

The above is the detailed content of Understanding Dijkstra&#s Algorithm: From Theory to Implementation. For more information, please follow other related articles on the PHP Chinese website!