ProgramGuru

Dijkstra's Algorithm Using Set - Shortest Path in Graph

Problem and examples

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.

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

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;

vector<int> dijkstra(int V, vector<vector<pii>>& adj, int S) {
    vector<int> dist(V, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[S] = 0;
    pq.push({0, S});

    while (!pq.empty()) {
        int d = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        for (auto& [neighbor, weight] : adj[node]) {
            if (d + weight < dist[neighbor]) {
                dist[neighbor] = d + weight;
                pq.push({dist[neighbor], neighbor});
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<pii>> adj = {
        {{1, 1}, {2, 4}},
        {{0, 1}, {2, 2}},
        {{0, 4}, {1, 2}}
    };

    vector<int> result = dijkstra(3, adj, 0);
    cout << "Shortest distances: ";
    for (int d : result) cout << d << " ";
    return 0;
}

Python implementation

import heapq

def dijkstra(V, adj, S):
    dist = [float('inf')] * V
    dist[S] = 0
    heap = [(0, S)]

    while heap:
        d, node = heapq.heappop(heap)
        for neighbor, weight in adj[node]:
            if d + weight < dist[neighbor]:
                dist[neighbor] = d + weight
                heapq.heappush(heap, (dist[neighbor], neighbor))

    return dist

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

print("Shortest distances:", dijkstra(3, adj, 0))

Java implementation

import java.util.*;

class Main {
    static class Pair {
        int node, dist;
        Pair(int d, int n) { dist = d; node = n; }
    }

    public static int[] dijkstra(int V, List<List<int[]>> adj, int S) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist));
        pq.add(new Pair(0, S));

        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            for (int[] edge : adj.get(p.node)) {
                int neighbor = edge[0], weight = edge[1];
                if (p.dist + weight < dist[neighbor]) {
                    dist[neighbor] = p.dist + weight;
                    pq.add(new Pair(dist[neighbor], neighbor));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        List<List<int[]>> adj = Arrays.asList(
            Arrays.asList(new int[]{1, 1}, new int[]{2, 4}),
            Arrays.asList(new int[]{0, 1}, new int[]{2, 2}),
            Arrays.asList(new int[]{0, 4}, new int[]{1, 2})
        );
        int[] result = dijkstra(3, adj, 0);
        System.out.print("Shortest distances: ");
        for (int d : result) System.out.print(d + " ");
    }
}

JavaScript implementation

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

  const visited = new Array(V).fill(false);

  for (let i = 0; i < V; i++) {
    let u = -1;
    for (let j = 0; j < V; j++) {
      if (!visited[j] && (u === -1 || dist[j] < dist[u])) u = j;
    }

    visited[u] = true;

    for (const [v, weight] of adj[u]) {
      if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
      }
    }
  }
  return dist;
}

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

console.log("Shortest distances:", dijkstra(3, adj, 0));

Go implementation

package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    node, dist int
}

type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)        { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func dijkstra(V int, adj [][][]int, S int) []int {
    dist := make([]int, V)
    for i := range dist {
        dist[i] = 1e9
    }
    dist[S] = 0
    h := &MinHeap{}
    heap.Push(h, Item{S, 0})

    for h.Len() > 0 {
        item := heap.Pop(h).(Item)
        for _, edge := range adj[item.node] {
            to, weight := edge[0], edge[1]
            if dist[item.node]+weight < dist[to] {
                dist[to] = dist[item.node] + weight
                heap.Push(h, Item{to, dist[to]})
            }
        }
    }
    return dist
}

func main() {
    adj := [][][]int{
        {{1, 1}, {2, 4}},
        {{0, 1}, {2, 2}},
        {{0, 4}, {1, 2}},
    }
    result := dijkstra(3, adj, 0)
    fmt.Print("Shortest distances: ", result)
}

Rust implementation

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn dijkstra(v: usize, adj: Vec<Vec<(usize, i32)>>, s: usize) -> Vec<i32> {
    let mut dist = vec![i32::MAX; v];
    let mut heap = BinaryHeap::new();
    dist[s] = 0;
    heap.push(Reverse((0, s)));

    while let Some(Reverse((d, u))) = heap.pop() {
        for &(v, w) in &adj[u] {
            if d + w < dist[v] {
                dist[v] = d + w;
                heap.push(Reverse((dist[v], v)));
            }
        }
    }

    dist
}

fn main() {
    let adj = vec![
        vec![(1, 1), (2, 4)],
        vec![(0, 1), (2, 2)],
        vec![(0, 4), (1, 2)],
    ];
    let result = dijkstra(3, adj, 0);
    println!("Shortest distances: {:?}", result);
}

Kotlin implementation

fun dijkstra(V: Int, adj: List<List<Pair<Int, Int>>>, S: Int): IntArray {
    val dist = IntArray(V) { Int.MAX_VALUE }
    dist[S] = 0
    val pq = java.util.PriorityQueue(compareBy<Pair<Int, Int>> { it.first })
    pq.add(0 to S)

    while (pq.isNotEmpty()) {
        val (d, node) = pq.poll()
        for ((neighbor, weight) in adj[node]) {
            if (d + weight < dist[neighbor]) {
                dist[neighbor] = d + weight
                pq.add(dist[neighbor] to neighbor)
            }
        }
    }
    return dist
}

fun main() {
    val adj = listOf(
        listOf(1 to 1, 2 to 4),
        listOf(0 to 1, 2 to 2),
        listOf(0 to 4, 1 to 2)
    )
    val result = dijkstra(3, adj, 0)
    println("Shortest distances: ${result.joinToString(" ")}")
}

Swift implementation

import Foundation

func dijkstra(_ V: Int, _ adj: [[(Int, Int)]], _ S: Int) -> [Int] {
    var dist = Array(repeating: Int.max, count: V)
    dist[S] = 0
    var pq = [(Int, Int)]()
    pq.append((0, S))

    while !pq.isEmpty {
        pq.sort { $0.0 < $1.0 }
        let (d, u) = pq.removeFirst()

        for (v, w) in adj[u] {
            if d + w < dist[v] {
                dist[v] = d + w
                pq.append((dist[v], v))
            }
        }
    }
    return dist
}

let adj = [
    [(1, 1), (2, 4)],
    [(0, 1), (2, 2)],
    [(0, 4), (1, 2)]
]
let result = dijkstra(3, adj, 0)
print("Shortest distances: \(result)")

TypeScript implementation

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

  const visited: boolean[] = new Array(V).fill(false);

  for (let i = 0; i < V; i++) {
    let u = -1;
    for (let j = 0; j < V; j++) {
      if (!visited[j] && (u === -1 || dist[j] < dist[u])) u = j;
    }

    visited[u] = true;

    for (const [v, weight] of adj[u]) {
      if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
      }
    }
  }
  return dist;
}

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

console.log("Shortest distances:", dijkstra(3, adj, 0));