# 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++) {
}
for(int edge[] : edges) {
}
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

We're building a next-level EdTech Startup.