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

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!

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!