Dijkstra’s Algorithm

Dijkstra’s Algorithm is one of the most important algorithms in Graph. It is also known as SSSP i.e. Single Source Shortest Path which is used to calculate shortest path between source to any destination node.

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 fromi to toi with weighti, 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]

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

Output:

0 2 6 5 4

Time Complexity:

O((V+E)logV), where E is the number of edges in the graph and V is the number of vertices in the graph.

Space Complexity:

O(V+E), where E is the number of edges in the graph and V is the number of vertices in the graph.

Innoskrit

Innoskrit

We're building a next-level EdTech Startup.

Related Posts

Leave A Reply

Your email address will not be published.