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.

Examples❯

Vertices (V)	Adjacency List	Source (S)	Output	Description
3	[[[1,1],[2,4]], [[0,1],[2,2]], [[0,4],[1,2]]]	0	[0,1,3]	Shortest paths from vertex 0 to 1 and 2
4	[[[1,5],[2,1]], [[0,5],[3,1]], [[0,1],[3,2]], [[1,1],[2,2]]]	0	[0,4,1,3]	Path from 0→2→3 is cheaper than 0→1→3
1	[[]]	0	[0]	Single node, distance to itself is 0
2	[[[1,10]], [[0,10]]]	1	[10,0]	Bidirectional edge with weight 10

Solution❯

Dijkstra's Algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. When implemented with a set, we can efficiently keep track of the minimum weight edge at each step.

The idea is to use a set to store pairs of (distance, vertex). At each step, we extract the node with the smallest tentative distance, then update the distances of its neighbors.

Initialize a distance array with infinity for all vertices, except the source which is 0.
Insert (0, source) into the set.
While the set is not empty:
- Extract the vertex with the smallest distance.
- For each neighbor, calculate the potential new distance.
- If this distance is smaller, update the distance and insert into the set.

This ensures that the shortest paths are computed efficiently, without revisiting already processed vertices unnecessarily.

Algorithm Steps❯

Create a distance array dist of size V, initialized to infinity. Set dist[S] = 0.
Create a set st and insert the pair (0, S).
While st is not empty:

Extract the pair (distance, node) with the smallest distance.
For each neighbor of node in adj[node]:

If dist[node] + edge_weight < dist[neighbor], update dist[neighbor] and insert (dist[neighbor], neighbor) into the set.

Return the dist array.

Code

JavaScript

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]

⬅ Previous TopicShortest Path in DAG using Topological Sort

Next Topic ⮕Dijkstra’s Algorithm Using Priority Queue