In Dijkstra's single source shortest path algorithm we try to find the shortest distance from one source to all other nodes in an undirected graph.
Note : We can't use the technique that we used earlier to find the shortest distance in an undirected graph where the edge weight was 1 unit. Since here the edge weight can be any number hence this approach will fail.
Note: Dijkstra's fails if the graph has negative edge weight or negative edge cycle( this will put the algo in loop leading to TLE)
What is Dijkstra's algorithm ?
Basically we start with the source node and we traverse to all the nodes making sure that all the nodes are reachable with the smallest possible distance from the source.
For Example :
Solution: Time complexity is approximately o(n+Elogn) (if we assume that edges E = no. of nodes n the it will be nlogn). n for breadth first traversal of the graph and, nlogn for using priority queue for sorting them in ascending order of there distance.
Space complexity is o(n) + o(n) (for distance array and priority queue)
//User function Template for Java
class Pair{
int key;
int value;
public Pair(){}
public Pair(int i, int j ){
this.key=i;
this.value = j;
}
public int getKey(){
return this.key;
}
public int getValue(){
return this.value;
}
}
class Solution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
{// we will use breadth first search for getting shortest path of all the nodes from
// source.
int distance[] = new int[V];
Arrays.fill(distance,Integer.MAX_VALUE);//initially all the distances are unknown from the source hence Integer.MAX_VALUE;
distance[S] = 0;//distance of source from source is 0
//since we take the not visited node with the smallest distance from the source(according to the Dijkstra's algorithm) hence
//this priority queue is needed that sorts the entries accordingly
//key = node, value = distance from the source
PriorityQueue<Pair> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
// adding the source node as the smallest distance node from the source (S,0)
q.add(new Pair(S,0));
while(!q.isEmpty()){
Pair p = q.remove();
for(ArrayList<Integer> l : adj.get(p.getKey())){
//for example u--->v (source--->adjacentNode)
// if() => distance[v]> dist(u,v) + valueOF(u); where valueOF(u) means cost to reach u from source
if(distance[l.get(0)]>l.get(1) + p.getValue()){
distance[l.get(0)] = l.get(1)+p.getValue(); // now this distace[v] has been calculated we can put
//it inside priority queue..
q.add(new Pair(l.get(0),distance[l.get(0)]));
}
}
}
return distance;//finally we can return distance;Integer.MAX_VALUE; it means that it is not reachable from the source node
}
}
Top comments (0)