Dijkstra’s Algorithm
Using Priority Queue

Problem Statement

You are given a weighted, undirected, and connected graph with V vertices represented using an adjacency list. Each entry adj[i] contains a list of lists, where each sublist contains two integers j and weight, representing an edge from vertex i to vertex j with a given weight.

Given a source vertex S, your task is to find the shortest distances from S to all other vertices using Dijkstra’s Algorithm and return them as a list.

Algorithm Steps

1. Initialize dist[] with Infinity, set dist[S] = 0.
2. Create a priority queue (min-heap) and insert {0, S}.
3. While the queue is not empty:
1. Pop the vertex with the minimum distance from the queue.
2. For each adjacent vertex v of the current node:
1. If dist[u] + weight < dist[v], update dist[v] and add {dist[v], v} to the queue.
4. Return dist[] as the shortest distances from source S.

Code

function dijkstra(V, adj, S) {
  const dist = new Array(V).fill(Infinity);
  dist[S] = 0;
  const minHeap = [[0, S]]; // [distance, vertex]

  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]);
    const [d, u] = minHeap.shift();

    for (const [v, wt] of adj[u]) {
      if (d + wt < dist[v]) {
        dist[v] = d + wt;
        minHeap.push([dist[v], v]);
      }
    }
  }

  return dist;
}

// Example:
const adjList = [
  [[1, 1], [2, 4]],
  [[0, 1], [2, 2]],
  [[0, 4], [1, 2]]
];
console.log("Shortest distances:", dijkstra(3, adjList, 0)); // Output: [0, 1, 3]