Dijkstra’s Algorithm Using Set - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

  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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 3

void dijkstra(int graph[V][V], int src, int dist[V]) {
    bool visited[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int min = INT_MAX, u = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v], u = v;
            }
        }

        visited[u] = true;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 4},
        {1, 0, 2},
        {4, 2, 0}
    };
    int dist[V];
    dijkstra(graph, 0, dist);

    printf("Shortest distances: ");
    for (int i = 0; i < V; i++) {
        printf("%d ", dist[i]);
    }
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...