Dijkstra’s Algorithm

Table Of Contents

Problem Statement:
Time Complexity:
Space Complexity:

Problem Statement:

You are given a positive integer n, edges, and src which represents number of nodes in a graph, list of edges where each edge represents from_i to to_i with weight_i, and source respectively. Your task is to return the shortest distance of each node from the src node.

Example:

Input: edges = [[0, 1, 2], [0, 2, 9], [0, 3, 8], [1, 2, 5], [1, 4, 2], [2, 3, 1], [3, 4, 1]], n = 5, src = 0
Output: [0, 2, 6, 5, 4]

Java

Python

C++

import java.util.*;

class Pair {
	int node, distance;
	public Pair(int node, int distance) {
		this.node = node;
		this.distance = distance;
	} 
}

class DijkstraAlgorithm {

	public static List<List<Pair>> buildGraph(int edges[][], int nodes) {

		List<List<Pair>> graph = new ArrayList<>();
		for(int i = 0; i < nodes; i++) {
			graph.add(new ArrayList<>());
		}
		for(int edge[] : edges) {
			graph.get(edge[0]).add(new Pair(edge[1], edge[2]));
			graph.get(edge[1]).add(new Pair(edge[0], edge[2]));
		}
		for(int i = 0; i < nodes; i++) {
			System.out.println(i + " : " + graph.get(i));
		}
		return graph;
	}

	public static int[] shortestPath(int edges[][], int nodes, int src) {
		List<List<Pair>> graph = DijkstraAlgorithm.buildGraph(edges, nodes);
		PriorityQueue<Pair> minHeap = new PriorityQueue<>((p1, p2) -> p1.distance - p2.distance);
		
		boolean visited[] = new boolean[nodes];
		int distance[] = new int[nodes];
		Arrays.fill(distance, Integer.MAX_VALUE);

		distance[src] = 0;
		minHeap.offer(new Pair(src, distance[src]));

		while(!minHeap.isEmpty()) {
			Pair pair = minHeap.poll();
			int currNode = pair.node;
			int currDistance = pair.distance;
			
			if(visited[currNode]) continue;
			
			visited[currNode] = true;

			for(Pair nbrPair : graph.get(currNode)) {
				if(visited[nbrPair.node]) continue;
				int newDistance = currDistance + nbrPair.distance;
				if(newDistance < distance[nbrPair.node]) {
					distance[nbrPair.node] = newDistance;
					minHeap.offer(new Pair(nbrPair.node, distance[nbrPair.node]));
				}
			}

		}
		return distance;
	}

	public static void main(String[] args) {
		int edges[][] = new int[][] {{0, 1, 2}, {0, 2, 9}, {0, 3, 8}, {1, 2, 5}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};

		int vertices = 5;
		int distance[] = shortestPath(edges, vertices, 0);
		for(int dist : distance) {
			System.out.print(dist + " ");
		}
	}
}

from heapq import *
import math

class DijkstraAlgorithm:

	def buildGraph(edges, nodes):
		graph = []
		for i in range(nodes):
			graph.append(list())
		for edge in edges:
			graph[edge[0]].append((edge[1], edge[2]))
			graph[edge[1]].append((edge[0], edge[2]))
		return graph

	def shortestPath(edges, nodes, src):
		graph = DijkstraAlgorithm.buildGraph(edges, nodes)
		min_heap = []
		
		visited = [False] * (nodes)
		distance = [math.inf] * (nodes)

		distance[src] = 0
		heappush(min_heap, (distance[src], src))

		while min_heap:
			curr_distance, curr_node = heappop(min_heap)
			if visited[curr_node]: continue
			
			visited[curr_node] = True

			for nbr_pair in graph[curr_node]:
        
				if visited[nbr_pair[0]]: continue
				new_distance = curr_distance + nbr_pair[1]
				if new_distance < distance[nbr_pair[0]]:
					distance[nbr_pair[0]] = new_distance
					heappush(min_heap, (new_distance, nbr_pair[0]))
			
		return distance

if __name__ == '__main__':
    edges = [[0, 1, 2], [0, 2, 9], [0, 3, 8], [1, 2, 5], [1, 4, 2], [2, 3, 1], [3, 4, 1]]
    v = 5
    src = 0
    ans = DijkstraAlgorithm.shortestPath(edges, v, src)
    print(ans)

#include<bits/stdc++.h>
using namespace std;

class DijkstraAlgorithm {

    struct comparator {
		bool operator() (pair<int, int> &a, pair<int, int> &b) {
			return a.second > b.second;
		}
	};

    public:

        static vector<vector<pair<int, int>>> buildGraph(int v, vector<vector<int>>& edges) {
            vector<vector<pair<int, int>>> graph;
            for(int i = 0; i < v; i++) {
                vector<pair<int, int>> nbr;
                graph.push_back(nbr);
            }
            for(auto edge : edges) {
                graph[edge[0]].push_back(make_pair(edge[1], edge[2]));
                graph[edge[1]].push_back(make_pair(edge[0], edge[2]));
            }

            return graph;
        }
        static vector<int> dijkstraAlgorithm(int v, vector<vector<int>> edges, int src) {
            vector<vector<pair<int, int>>> graph = DijkstraAlgorithm::buildGraph(v, edges);
            priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> minHeap;
            vector<int> distance(v, INT_MAX);
            vector<bool> visited(v, false);
            
            distance[src] = 0;
            minHeap.push(make_pair(src, 0));

            while(!minHeap.empty()) {
                pair<int, int> node = minHeap.top();
                minHeap.pop();
                int currNode = node.first;
                int currDistance = node.second;
                if(visited[currNode]) continue;
                
                visited[currNode] = true;
            
                for(auto nbrPair : graph[currNode]) {
                    if(visited[nbrPair.first]) continue;
                    int newDistance = currDistance + nbrPair.second;
                    if(newDistance < distance[nbrPair.first]) {
                        distance[nbrPair.first] = newDistance;
                        minHeap.push(make_pair(nbrPair.first, newDistance));
                    }
                }
            }
            return distance;
        }
};

int main(int argc, char const *argv[]) {
    int v = 5;
    vector<vector<int>> edges{{0, 1, 2}, {0, 2, 9}, {0, 3, 8}, {1, 2, 5}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
    int src = 1;
    vector<int> ans = DijkstraAlgorithm::dijkstraAlgorithm(v, edges, src);
    for(int i = 1; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    return 0;
}