Dijkstra’s Algorithm
Using Set in Graphs

Problem Statement

You are given a weighted, undirected, and connected graph with V vertices. The graph is represented as an adjacency list adj where adj[i] is a list of lists. Each list contains two integers: the first is a connected vertex j and the second is the weight of the edge from i to j.

Given a source vertex S, the task is to find the shortest distance from the source to every other vertex. The output should be a list of integers denoting these shortest distances.

Algorithm Steps

1. Create a distance array dist of size V, initialized to infinity. Set dist[S] = 0.
2. Create a set st and insert the pair (0, S).
3. While st is not empty:
1. Extract the pair (distance, node) with the smallest distance.
2. For each neighbor of node in adj[node]:
1. If dist[node] + edge_weight < dist[neighbor], update dist[neighbor] and insert (dist[neighbor], neighbor) into the set.
4. Return the dist array.

Code

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

  const set = new Set();
  set.add([0, S]);

  const compare = (a, b) => a[0] - b[0];

  while (set.size > 0) {
    let [d, node] = [...set].sort(compare)[0];
    set.delete([d, node]);

    for (const [neighbor, weight] of adj[node]) {
      if (d + weight < dist[neighbor]) {
        set.add([dist[neighbor], neighbor]); // Remove old
        dist[neighbor] = d + weight;
        set.add([dist[neighbor], neighbor]);
      }
    }
  }

  return dist;
}

const adj = [
  [[1, 1], [2, 4]],
  [[0, 1], [2, 2]],
  [[0, 4], [1, 2]]
];

console.log("Shortest distances:", dijkstra(3, adj, 0)); // Output: [0, 1, 3]