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.
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.
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
O((V+E)logV)
, where E
is the number of edges in the graph and V
is the number of vertices in the graph.
O(V+E)
, where E
is the number of edges in the graph and V
is the number of vertices in the graph.
© 2022 - All Rights Reserved.