ProgramGuru

Dijkstra’s Algorithm Using Priority Queue

Problem and examples

You are given a weighted, undirected, and connected graph with V vertices represented using an adjacency list. Each entry adj[i] contains a list of lists, where each sublist contains two integers j and weight, representing an edge from vertex i to vertex j with a given weight.

Given a source vertex S, your task is to find the shortest distances from S to all other vertices using Dijkstra’s Algorithm and return them as a list.

Vertices Adjacency List Source Shortest Distances
3 [ [ [1, 1], [2, 4] ], [ [0, 1], [2, 2] ], [ [0, 4], [1, 2] ] ] 0 [0, 1, 3]
2 [ [ [1, 5] ], [ [0, 5] ] ] 1 [5, 0]
1 [ [] ] 0 [0]
4 [ [ [1, 2] ], [ [0, 2], [2, 1] ], [ [1, 1], [3, 5] ], [ [2, 5] ] ] 0 [0, 2, 3, 8]

How it works

Understanding the Problem

We are given a weighted graph and a starting node (source). Our goal is to find the shortest distance from this source to all other nodes in the graph.

In other words, for every node in the graph, we want to calculate the minimum possible sum of edge weights required to reach that node from the source.

This problem is a classic case of finding single-source shortest paths in graphs with non-negative weights, and Dijkstra’s Algorithm is an efficient way to solve it using a priority queue.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let's consider the following weighted graph with 5 nodes (0 to 4), and the edges:


0 --(2)--> 1
0 --(4)--> 2
1 --(1)--> 2
1 --(7)--> 3
2 --(3)--> 4
3 --(1)--> 4

We want to find the shortest distance from node 0 to all other nodes.

Step 2: Initialize the Distance Array

Create a distance[] array and fill it with Infinity to represent that we don’t yet know the shortest path. Set the distance of the source node to 0.


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

Step 3: Use a Min-Heap (Priority Queue)

Use a priority queue (min-heap) to always pick the next node with the smallest known distance. Initially, insert the source node with distance 0:


priorityQueue = [(0, 0)]  // (distance, node)

Step 4: Start the Main Loop

While the priority queue is not empty:

  1. Extract the node with the smallest distance.
  2. Explore all its neighbors.
  3. If a shorter path to a neighbor is found, update the distance and insert it into the queue.

Step 5: Trace the Execution for Our Example

  • Start with node 0, distance 0.
  • Check edges: (0 → 1, weight 2), (0 → 2, weight 4)
  • Update: distance[1] = 2, distance[2] = 4
  • Queue: [(2,1), (4,2)]
  • Next node: 1, distance 2
  • Check edges: (1 → 2, weight 1) → 2 + 1 = 3 is better than current 4, update distance[2] = 3
  • Also (1 → 3, weight 7) → distance[3] = 9
  • Queue: [(3,2), (4,2), (9,3)]
  • Next node: 2, distance 3
  • Check edge (2 → 4, weight 3) → distance[4] = 6
  • Queue: [(4,2), (9,3), (6,4)]
  • Next node: 4, distance 6 → Already the best.
  • Check edge (4 → 3, weight 1) → 6 + 1 = 7 is better than 9 → update distance[3] = 7

Step 6: Final Distance Array


distance = [0, 2, 3, 7, 6]

This gives the shortest path from node 0 to every other node in the graph.

Edge Cases

  • Disconnected Graph: If a node is not reachable from the source, its distance will remain Infinity.
  • Zero Weight Edges: Dijkstra’s algorithm handles them correctly as long as weights are non-negative.
  • Multiple Edges Between Nodes: Always consider the one with the minimum weight during edge relaxation.
  • Self-loops: They can be ignored unless required for the specific application.

Finally

Dijkstra’s Algorithm is a powerful tool for finding the shortest paths in a graph with non-negative weights. Using a priority queue helps efficiently expand the closest node at every step. Always remember to initialize distances properly and carefully update them when a shorter path is found. This algorithm is widely used in routing, pathfinding, and network optimization problems.

  1. Initialize dist[] with Infinity, set dist[S] = 0.
  2. Create a priority queue (min-heap) and insert {0, S}.
  3. While the queue is not empty:
    1. Pop the vertex with the minimum distance from the queue.
    2. For each adjacent vertex v of the current node:
      1. If dist[u] + weight < dist[v], update dist[v] and add {dist[v], v} to the queue.
  4. Return dist[] as the shortest distances from source S.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 3

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v], min_index = v;
        }
    }
    return min_index;
}

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

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

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

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

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

int main() {
    int graph[V][V] = {
        {0, 1, 4},
        {1, 0, 2},
        {4, 2, 0}
    };
    dijkstra(graph, 0);
    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 u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        for (auto edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (d + weight < dist[v]) {
                dist[v] = d + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

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

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

Python implementation

import heapq

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

    while min_heap:
        d, u = heapq.heappop(min_heap)
        for v, wt in adj[u]:
            if d + wt < dist[v]:
                dist[v] = d + wt
                heapq.heappush(min_heap, (dist[v], v))

    return dist

adj_list = [
    [[1, 1], [2, 4]],
    [[0, 1], [2, 2]],
    [[0, 4], [1, 2]]
]
print("Shortest distances:", dijkstra(3, adj_list, 0))

Java implementation

import java.util.*;

public class DijkstraExample {
    static class Pair {
        int vertex, weight;
        Pair(int v, int w) {
            vertex = v;
            weight = w;
        }
    }

    public static int[] dijkstra(int V, List<List<Pair>> 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.weight));
        pq.offer(new Pair(S, 0));

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            for (Pair neighbor : adj.get(current.vertex)) {
                if (current.weight + neighbor.weight < dist[neighbor.vertex]) {
                    dist[neighbor.vertex] = current.weight + neighbor.weight;
                    pq.offer(new Pair(neighbor.vertex, dist[neighbor.vertex]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int V = 3;
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(new Pair(1, 1));
        adj.get(0).add(new Pair(2, 4));
        adj.get(1).add(new Pair(0, 1));
        adj.get(1).add(new Pair(2, 2));
        adj.get(2).add(new Pair(0, 4));
        adj.get(2).add(new Pair(1, 2));

        int[] result = dijkstra(V, adj, 0);
        System.out.println("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 minHeap = [[0, S]];

  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]);
    const [d, u] = minHeap.shift();

    for (const [v, wt] of adj[u]) {
      if (d + wt < dist[v]) {
        dist[v] = d + wt;
        minHeap.push([dist[v], v]);
      }
    }
  }

  return dist;
}

const adjList = [
  [[1, 1], [2, 4]],
  [[0, 1], [2, 2]],
  [[0, 4], [1, 2]]
];
console.log("Shortest distances:", dijkstra(3, adjList, 0));

Go implementation

package main

import (
    "container/heap"
    "fmt"
    "math"
)

type Edge struct {
    to, weight int
}

type Item struct {
    node, dist int
}

type PriorityQueue []Item

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

func dijkstra(V int, adj [][]Edge, S int) []int {
    dist := make([]int, V)
    for i := 0; i < V; i++ {
        dist[i] = math.MaxInt64
    }
    dist[S] = 0
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{S, 0})

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

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

Rust implementation

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

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

    while let Some(Reverse((d, u))) = heap.pop() {
        for &(vtx, wt) in &adj[u] {
            if d + wt < dist[vtx] {
                dist[vtx] = d + wt;
                heap.push(Reverse((dist[vtx], vtx)));
            }
        }
    }
    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

import java.util.*

data class Edge(val node: Int, val weight: Int)

def dijkstra(V: Int, adj: List<List<Edge>>, src: Int): IntArray {
    val dist = IntArray(V) { Int.MAX_VALUE }
    val pq = PriorityQueue(compareBy<Pair<Int, Int>> { it.first })
    dist[src] = 0
    pq.offer(Pair(0, src))

    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        for (edge in adj[u]) {
            if (d + edge.weight < dist[edge.node]) {
                dist[edge.node] = d + edge.weight
                pq.offer(Pair(dist[edge.node], edge.node))
            }
        }
    }
    return dist
}

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

Swift implementation

import Foundation

struct Edge {
    let to: Int
    let weight: Int
}

func dijkstra(V: Int, adj: [[Edge]], source: Int) -> [Int] {
    var dist = Array(repeating: Int.max, count: V)
    dist[source] = 0
    var heap = [(0, source)]

    while !heap.isEmpty {
        heap.sort { $0.0 < $1.0 }
        let (d, u) = heap.removeFirst()
        for edge in adj[u] {
            if d + edge.weight < dist[edge.to] {
                dist[edge.to] = d + edge.weight
                heap.append((dist[edge.to], edge.to))
            }
        }
    }
    return dist
}

let adj: [[Edge]] = [
    [Edge(to: 1, weight: 1), Edge(to: 2, weight: 4)],
    [Edge(to: 0, weight: 1), Edge(to: 2, weight: 2)],
    [Edge(to: 0, weight: 4), Edge(to: 1, weight: 2)]
]

let result = dijkstra(V: 3, adj: adj, source: 0)
print("Shortest distances:", result)

TypeScript implementation

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

  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]);
    const [d, u] = minHeap.shift()!;

    for (const [v, wt] of adj[u]) {
      if (d + wt < dist[v]) {
        dist[v] = d + wt;
        minHeap.push([dist[v], v]);
      }
    }
  }

  return dist;
}

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

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