Dijkstra's Algorithm

Dijkstra's Algorithm

Welcome to Dijkstra's Algorithm, a cornerstone of graph theory. Named after computer scientist Edsger W. Dijkstra, this algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

---

1. The Core Idea: A Greedy Approach

Dijkstra's algorithm works by being "greedy." It always focuses on the vertex that is currently closest to the source and has not yet been finalized. It maintains a set of "settled" vertices (for which the shortest path is known) and a set of "unsettled" vertices.

At each step, it selects the unsettled vertex with the smallest known distance from the source and declares its path to be final. It then uses this vertex to potentially update the distances to its neighbors.

This process is made efficient by using a Min-Priority Queue, which allows us to quickly retrieve the unsettled vertex with the minimum distance.

---

2. The Algorithm Step-by-Step

1. Initialization:

   • Create a distances array and initialize the distance to the source vertex as 0 and all other distances to infinity.
   • Create a parent array to reconstruct paths later, initializing all entries to null.
   • Create a min-priority queue and add the source vertex to it with a priority of 0.

2. Processing Loop:

   • While the priority queue is not empty:
     • Extract Min: Remove the vertex u with the smallest distance from the priority queue.
     • Check for Stale Entry: If u has already been processed with a shorter path, skip it.
     • Relax Edges: For each neighbor v of u with edge weight w:
       • If distances[u] + w < distances[v], it means we have found a shorter path to v.
       • Update distances[v] = distances[u] + w.
       • Update parent[v] = u.
       • Add v to the priority queue with its new, shorter distance as its priority.

3. Completion:

   • When the loop finishes, the distances array will contain the shortest path distances from the source to all other vertices.

---

3. Implementation with a Priority Queue

// Assumes a MinPriorityQueue class is available
function dijkstra(adj, src) {
  const N = adj.length;
  const dist = Array(N).fill(Infinity);
  const parent = Array(N).fill(-1);
  const pq = new MinPriorityQueue({ priority: (item) => item.priority });

  dist[src] = 0;
  pq.enqueue({ vertex: src, priority: 0 });

  while (!pq.isEmpty()) {
    const { vertex: u, priority: d } = pq.dequeue();

    // If we've found a shorter path already, skip this one
    if (d > dist[u]) {
      continue;
    }

    for (const { neighbor: v, weight: w } of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        pq.enqueue({ vertex: v, priority: dist[v] });
      }
    }
  }
  return { dist, parent };
}

---

4. Complexity Analysis

• Time Complexity: O((N + M) log N) with a binary heap-based priority queue, where N is the number of vertices and M is the number of edges. The log N factor comes from the priority queue operations (enqueue and dequeue).
• Space Complexity: O(N) to store distances, parents, and the priority queue.

---

5. Key Considerations

• Non-Negative Weights: Dijkstra's algorithm's greedy approach only works if all edge weights are non-negative. If there are negative weights, it may produce incorrect results. For such cases, the Bellman-Ford algorithm is required.
• Stale Entries: In the implementation, you might add multiple entries for the same vertex to the priority queue if you find several paths to it. The check if (d > dist[u]) continue; is crucial to ignore these "stale" entries and only process the one with the shortest path found so far.

---

Key Takeaway: Dijkstra's algorithm is the go-to solution for finding the shortest paths in graphs with non-negative weights. It uses a greedy strategy, made efficient by a priority queue, to explore the graph and guarantees finding the optimal path with a time complexity of O((N + M) log N).