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❯

Understanding the Problem

We are given a weighted graph with non-negative edge weights, and our goal is to find the shortest paths from a source vertex to all other vertices. This is a classic single-source shortest path problem.

To solve it, we’ll use Dijkstra’s Algorithm, which is efficient and guarantees the shortest path when weights are non-negative. In this version, we will implement it using a set data structure, which helps us quickly get the vertex with the current minimum tentative distance.

Step-by-Step Solution with Example

Step 1: Initialize Distance Array

Let’s consider a sample graph:


0 --1--> 1
0 --4--> 2
1 --2--> 2
1 --6--> 3
2 --3--> 3

The graph has 4 nodes (0 to 3) and weighted edges. We'll find the shortest path from node 0 to all others.

Start by initializing a distance[] array with infinity for all nodes, except the source node (0), which will be 0:

distance[] = [0, ∞, ∞, ∞]

Step 2: Insert Source into Set

We use a set of pairs (distance, node). Start with:

set = {(0, 0)}

Step 3: Extract Node with Minimum Distance

Pick the node with the smallest distance from the set, which is (0, 0). Visit all its neighbors:

To node 1: distance = 0 + 1 = 1 → Update and insert (1, 1)
To node 2: distance = 0 + 4 = 4 → Update and insert (4, 2)

distance[] = [0, 1, 4, ∞]
set = {(1, 1), (4, 2)}

Step 4: Process Next Node

Pick (1, 1). Neighbors:

To node 2: 1 + 2 = 3 → Better than 4, update (remove 4,2) and insert (3, 2)
To node 3: 1 + 6 = 7 → Update and insert (7, 3)

distance[] = [0, 1, 3, 7]
set = {(3, 2), (7, 3)}

Step 5: Process Node 2

Pick (3, 2). Neighbors:

To node 3: 3 + 3 = 6 → Better than 7, update (remove 7,3) and insert (6, 3)

distance[] = [0, 1, 3, 6]
set = {(6, 3)}

Step 6: Process Final Node

Pick (6, 3). No updates as all neighbors already have optimal distances. Done.

Edge Cases

Disconnected Nodes: Some nodes may not be reachable. Their distances will remain infinity.
Multiple Edges: If multiple edges exist between two nodes, consider the one with minimum weight.
Self-loops: These don’t help in pathfinding and can be ignored.
Negative Weights: Dijkstra’s algorithm does not work correctly with negative edge weights. Always validate input.

Finally

Dijkstra’s algorithm is a powerful and efficient method for solving shortest path problems in graphs with non-negative weights. By using a set, we can maintain and access the node with the minimum tentative distance in logarithmic time, making the algorithm efficient for sparse graphs.

For dense graphs or when performance is critical, using a priority queue (min-heap) might be even faster. However, the set-based approach remains intuitive and easy to implement.

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

Comments

Loading comments...