Hello friends. my name is Tushar and today we are going to talk about single source shortest path
using Dijkstra's Algorithm. So, what is single source shortest path? so, you are given a graph and
you are gven a source vertex, and you have to find the shortest path of every other vertex from this
source vertex . So, for example, here, i have this very simple graph and my source vertex is A. and i have
to find the distance, the shortest distance of every other vertex from A. So, for example, C, C can be
reached from A->B->C or A->F->C or A->D->F->C, so, the shortest distance here is via B and the distance
is six. Similarly, E can be reached via A->F->D->E or A->D->E and the shortest distance here is this
and again the distance is six. So, Dijkstra's Algorithm works both on directed and undirected
graph as long as the weight on the edge is non-negative number. Also, Dijkstra's Algorithm is a
greedy algorithm and it is very very similar to Prim's Algorithm of finding Minimum Spanning Tree,
which i have already discussed in another video. Also, for Dijkstra's Algorithm, we need this Data
Structure, Heap plus Map which supports these four operations. add, extractMin, contains and decrease
key and i have already talked about this Data Structure in Prim's Algorithm. This Data Structure
is nothing but a combination of a Binary Heap and a Hash Map and the link to that video is also attached
in this video here. So, watch that video first before watching this algorithm here. So, now, in
the next section, let's see how Dijkstra's Algoithm works. So, we are able to run Dijkstra's Algorithm
on this undirected graph here. Here, the source vertex is A and we are trying to find the shortest
distance of every other vertex from A. So, the way this algorithm works is, I have this Heap plus Map
Data Structure and then i am going to put all these vertices in this Data Structure with the distance
infinity from A. because i dont know how far they are from A at this point of time. Then, we are going
to set A's distnce to zero because A is at distance zero from itself and then we're going to do an
extractMin here to basically get A out and then explore all its neighbours and update their distance
from A. So, we will get B,D,E and updae their distance, so, B five, D nine and then E two from A
and then i will do another extractMin, so, get E out and explore its neighbours, so, that's F and the
distance of F from A will be whatever the distance E is from A and plus this weight here, so, that's
five, so put five there in place of F and then keep doing this extractMin until we have elements in this
Data Structure here. This Distance Map is going to store the distance, the shortest distance of the
vertex from A while this path Map is going to help us trace back the path, the shortest path from A to
every vertex. So, let's do a Dry Run of this algorithm on this graph here. So, initially, our
source vertex is A, so, we will put this value as zero, then we do an extractMin here and then we make
our current as A, so then we are going to explore neighbours of A. So, the first neighbour of A is B,
so, let's first remove A from here and then update A's distance as zero and A's parent as null because
A is the source vertex. Then, we are going to explore neighbours of A, so first neighbour of A is
B, so, B exists in this map here, yes, and then the distance attached with B is greater than this edge
weight here, so we will update this distance to this, basically saying that we found a path which is
shorter than what you know right now, so, we will update this to five. Then we are going to explore.
Also, we are going to say that B's current value is coming from A. Also, then we are going to explore
another neighbour, so, D and then the current distance attached with D is infinity, while this
edge, while this guy says that you can reach D from A in distance nine, so, we will update this with nine
and also say that this nine is coming from A. So, D is also coming directly from A and then explore
another neighbour, E, so the distance of E from A is two and E exists here, so we will replace this with
two and we will say that E is also coming from A. So, at this point of time, A is done exploring all
its neighbours, so, we are going to go in here again and do another extractMin. So, the least value here
is E, so we'll take E out,so our current will become E and we will take E out and put its distance as two
and now we will explore neighbours of E. So, the first neighbour of E is A and A doesn't exist in
this Heap plus Map Data Structure, so we ignore A and then the second neighbour of E is F and F does
exist here and the value attached with F is infinity while if we went via E, it can reach A in distance
two, whatever the minimum distance it takes to reach E plus the weight of this edge. So, value of F goes
to five. Two plus three five. So, also we are going to say that F got introduced by E. So, at this point
of time, we are done exploring all the neighbours of E, so we are again going to do an extractMin on this
Data Structure. So, we can pick either of them, so, let's pick B and say that B's minimum distance from
A is five and okay, so, we will explore neighbours of B, so, first neighbour of B is A but A doesn't
exist here, so, we will just ignore A and then another neighbour of B is C and C does exist here and
the value attached with C is infinity while if we go via route B, then it can reach A in distance two
plus whatever is attached with B, so, that's two plus five seven and then we're going to say that C
got introduced by B. At this point of time, B doesn't have any other neighbours. So, we are again
going to go and do an extractMin here. So, this time, five comes out because five is the least value
of all three. So, F is the least value of all three, so, F comes out and we are going to update F's
distance to five and then we are going to explore neighbours of F. So, first neighbour of F is E but E
doesn't exist in this map here,so, we're going to ignore E because we've already found the shortest
distance of E from A. Then we are going to explore another neighbour which is D, so currently D does
exist here and currently we found one path to D via this route but if we took this route, basically this
route, we can reach D in a shorter Distance because we can reach F in distance five and from F to D, it
will take five plus two seven, so, that distance is shorter than what it is right now, so, we will
replace D with seven. So, before D could be reached with distance nine but if we took this path via F
and F can be reached in five and weight of this edge is two. So, we can reach D in seven. So, we're going to
go here and say that now D's parent is F because that's the guy who introduced seven for D. Then, now
F has no more neighbours to explored, so we will again go and do an extractMin here. So, let's say we got C
out. So, out current neighbour is C, our current value is C and we will say C is seven. So, now we will explore
neighbours of C. So, first neighbour of C is B and B is not here, so we will ignore B. Another neighbour of C
is D and the value to reach D via C will be whatever it takes to reach C which is seven plus the weight of this
edge which is ten which is greater than what we have here. So, there is no reason to reach D via this route,
so, we will just ignore that value. So, we're done exploring all the neighbours of C, so finally, we're
going to do an extractMin here and our current will become D and we will update D with seven and then D
will explore its neighbours, A which is not there, F which is also not there and C which is also not there.
So, at this point of time, we are done with the Algorithm because this Data Structure is now empty. So,
this is the distance of every vertex from A. E is at distance two, F is at distance five, B is at distance
five, C is at distance seven and D is at distance seven.If you wanted to find the path, like how do i
know which path to take to reach D from A. So, we just go here and go to D and D is coming from F. So, we go
to F and F is coming from E, then we go to E and E is coming from A. So, we can clearly take this path to
reach A from D. Another example is if you want to know how to reach C, so,we go here, C is coming from B, so C
is coming from B and then B is coming from A, so, B is coming from A, so we take this path to reach C. So the
time complexity for this algorithm is similar to Prim's Algorithm which is O(Elog(V)). The reason is, we're
going to apply this, the size of this data structure in the worst case is going to be V and then we're going
to apply decreaseKey, extractMin on this data structure E times which is the total number of edges and V is the
total number of vertices. So, the time complexity will be O(ElogV) and the space complexity will be O(E+V)
because we might have to store as many edges or all vertices in this 3 data structures here. So, in the
next section, let's quickly look at the code for this algorithm.
Name of the function is shortestPath. It takes in a graph and sourceVertex from which we want to find
the shortest distance of every other vertex. Then, it returns a map of vertex and the shortest distance of
that vertex from the source vertex. And then let's initialize our data structure. The first one is a Heap
+ Map data structure which supports extractMin, add, decrease and contains operation and then second data
structure is a map which stores the shortest distance from source vertex to every vertex and then this one is
a parent which is useful for tracing the shortest path from source vertex to every vertex. First thing we do
is, we initialize all the vertices with infinite value as we discussed before in the video. Then, we are going
to decrease the value of source vertex to zero because source vertex is at distance zero from itself and then
put this value in the distance map and also set the parent of source vertex as null. Now, we're going to
iterate through minHeap until minHeap has elements in it. So, then we're going to extract minimum value
vertex from this minHeap and it returns me a Heap node which has both actual vertex and distance of
that vertex from the source vertex. Once we get this heap node, we get the current vertex from it and also
update the distance map, in distance map, we put this current vertex and the distance of this vertex from the
source vertex. Then, we're going to iterate through all its neighbours one by one, so, we get its adjacent
vertex, then what we're gonna check is if the adjacent vertex is present in the minHeap or not. If the adjacent
vertex is not present in minHeap, it means that we've already found out the shortest distance of that adjacent
vertex from the source vertex. So, there is nothing to do for this adjacent vertex. So, we just continue and go
back to the top of the for loop and look for the next adjacent vertex. If the minHeap does contain the
adjacent vertex, so we come to this point and try to find the distance of that adjacent vertex from the
source vertex while going through this current vertex. So, distance.get(current)is going to give me minimum
distance of the current vertex from the source vertex and edge.getWeight() is going to give me the distance
between the current vertex and the adjacent vertex. So, this new distance is the total distance from source
vertex to the adjacent vertex, going through this current vertex. What we're going to do is check if
the value stored in the minHeap, the distance stored in the minHeap for the adjacent vertex, if it is greater
than this newDistance, then we're going to decrease the value in the minHeap to this new distance and also
update the parent of the adjacent vertex to current vertex and then, we're going to look at the next
adjacent vertex and once we are done exploring all neighbours, we just go back to top of this while loop
and do extractMin and repeat the same process for another vertex and we keep doing this till the Heap is
not empty and in the end, all we do is return this distance which has distance of every vertex from the
source vertex. So, this is all i have to talk about Dijkstra's Algorithm. The link to this code is in the
description secton of the video. Please like this video, share this video, comment on this video,
check out my fb page, facebook.com/tusharroy25 and checkout my github link
github.com/mission-peace/interview/wiki
Thanks again for watching this video.