7
Oct

Dijkstra’s Algorithm In Java (Theory + Code Implementation)


In Dijkstra’s algorithm, we find shortest
distance from source vertex to all other vertices in the graph. It gives correct
results only if all the edge weights are non-negative. Example, in this graph if
you take zero as the source vertex then using Dijkstra’s algorithm we can find
shortest path and shortest distance from vertex zero to all other vertices of the
graph. Now let’s see how Dijkstra’s algorithm works. We’ll give each vertex a
status. This status can be temporary or permanent. If the status of a vertex is
temporary, it means the shortest path to it has not been finalized and if the
vertex is permanent it means that the shortest path to it has been finalized.
Now initially all vertices have temporary status and in each step of the
algorithm we’ll change the status of a vertex from temporary to permanent that
is in each step we’ll finalize the shortest path to a vertex of the graph. Each vertex will be labeled with path length
and predecessor. At any point of the algorithm, path
length of a temporary vertex denotes the length of shortest path from source
vertex to any vertex v known till now, means known till that point of the
algorithm. As the algorithm proceeds we might get a better path from source vertex to
vertex v and in that case we’ll change the value of this path length.
A predecessor of a temporary vertex denotes the predecessor of v in the
shortest path known till now. For a permanent vertex
this path length denotes the length of shortest path from source vertex to v
and predecessor denotes the predecessor of v in the shortest path. Now when the
algorithm starts the path length of all vertices is initialized to infinity
which denotes a very large number and predecessor of all vertices is
initialized to NIL. This NIL can be any number that does not denote a vertex. Our
vertex numbers start from 0, so we will take this NIL to be -1.
During the algorithm the path length and predecessor of a temporary vertex can
be changed many times. Whenever we’ll get a shorter path we’ll update these values.
When we change these values for our vertex we’ll say that we are relabeling
that vertex. So a temporary vertex can be relabeled but once the vertex is made
permanent it will not be relabeled because shortest path to it has been finalized. We have seen that initially all vertices
will be temporary and in each step of the algorithm we’ll make a temporary vertex permanent. Now to choose the vertex that is to be
made permanent we use the greedy approach. In greedy approach, we generally
perform an action that appears best at the moment. So in this algorithm we’ll
take that temporary vertex with minimum path length and make it permanent.
Now let’s see the whole step wise procedure of the algorithm. Initially for all vertices path length
is equal to infinity, predecessor is NIL and status is Temporary.
Now first we make the path length of source vertex equal to 0. Now from all
the temporary vertices of the graph we’ll find the temporary vertex which is
minimum path length and we’ll make it permanent and it becomes the current
vertex. At the start of the algorithm source vertex is minimum path length, so
the source vertex will be the first one to become permanent. In the second step,
we’ll examine all temporary vertices adjacent to the current vertex and we’ll
relabel them if required. Now let’s see what’s the condition when we need to
relabel any temporary vertex adjacent to current vertex. Suppose v is a
temporary vertex adjacent to current vertex that we are examining. Now if path
length of current vertex plus weight on this edge is less than path length of
vertex v then we’ll relabel the vertex v. Now path length of v becomes equal to
path length of current plus weight on this edge and now current becomes the
new predecessor of vertex v. If this value is greater than path
length of v then no relabeling is required.
Now these steps one and two are repeated till either there are no temporary
vertices left in the graph or all the temporary vertices that are left have
path length equal to infinity. At the end of the algorithm the temporary vertices
that are left with path length infinity are those vertices that are not
reachable from the source vertex. Now let’s understand with the help of a figure
how this relabeling of a temporary vertex is done in this step two. Suppose s is the source vertex and c is
the vertex which we have recently made permanent, so it is the current vertex,
these are the labels. Labels of permanent vertices are fixed, they’re never changed.
Now this 6 is the value of the path length, so it is actually the length of
the shortest path from source to this vertex. This vertex c is permanent, it
means that this shortest path to c is final. Now predecessor of this vertex c in the shortest path is vertex p. Now we have to examine the temporary
vertices that are adjacent to this current vertex.
Suppose we have these three temporary vertices adjacent to this vertex c and
these are the labels. Now these are temporary vertices so
their labels are not fixed we can change them whenever we get a shorter path
First let’s examine this vertex v1. Path length for it is 10, it means that
till now the shortest path that we know from s to v1 is of length 10
and the predecessor of v1 on this path is vertex x.
Now we check this condition for this vertex v1. Path length of current
vertex is 6, path length of v1 is 10 and the weight on this edge is 2. Now 6 + 2
is less than 10, so this condition is true.
It means that we have found a shorter path to vertex v1. Till now we knew
that shortest path to v1 was of length 10. Now we have a path of length 8, which
is made up of two parts, a path from s to c and an edge from c to v1. So we relabel this vertex v1. Now
value of path length is 8 and c is the predecessor of vertex v1 in the shortest path. Now let’s examine this vertex v3.
Path length of v3 is 8, it means that till now the shortest path that we know
from s to v3 is of length 8 and the predecessor of v3 on this path is
vertex y. Now let’s check this condition. Path length of this current vertex is
6, path length of this vertex v3 is 8 and the
wait on this edge is 3. Now 6 + 3 is greater than 8. So this condition is not
true. So there is no relabeling required for this vertex v3. It means
that using this vertex c, we did not get a better path to vertex v3. This path
was of length 8 and this path that we get using this vertex c was of length 9.
So we did not change the label of this vertex v3. Now let’s see this vertex v2.
Now for this vertex v2, path length is infinity and predecessor is NIL. It means
that we have not found any path till now from s to vertex v2. So definitely
this condition will be true, 6+5 is less than infinity so we will relabel this vertex v2. Now in the next video, we’ll take a graph
and understand the whole procedure. In this video, we’ll understand the
procedure of Dijkstra’s algorithm with the help of this graph. Now initially all
vertices are temporary, path length of all vertices is infinity and predecessor
for all vertices is NIL. Now we’ll take vertex 0 as the source vertex. So
at the end of the algorithm we’ll be able to find shortest path from this
vertex 0 to all other vertices of the graph. Now the first step is to make path
length of source vertex 0, so we make path length of this vertex 0 equal
to 0. Now from all the temporary vertices we have to find the vertex
which has minimum path length. So this vertex 0 is a vertex with the minimum
path length, so we’ll make it permanent. Now this vertex 0 is a current vertex. Now
we have to examine all the temporary vertices that are adjacent to this
vertex 0. So these are the temporary vertices 1, 3 & 4 which are adjacent to
this vertex 0. So now we’ll examine these vertices one by one.
Now first we’ll examine this vertex 1, path length of this vertex 0 plus
weight on this edge is less than path length of vertex 1, so we’ll relabel
this vertex 1. Now 5 is a path length of vertex 1 and 0 is its predecessor. Let’s we take this vertex 3, path
length of vertex 0 plus weight on this edge is less than path length of vertex
3, so we’ll relabel this vertex. Now 2 is the path length of this vertex
3 and 0 is its predecessor. Similarly we’ll take this vertex 4
and it will be relabeled. Now from all the temporary vertices we
have to choose the vertex that is minimum path length. This vertex 3 is a
vertex with a minimum path length, so we’ll make vertex 3 permanent. Now this
vertex 3 is our current vertex. We have to examine all the temporary vertices
that are adjacent to vertex 3. Vertices adjacent to vertex 3 are 4 and 6, and both
of them are temporary. So we will examine vertices 4 & 6. First we take this vertex
4, now path length of 3 plus weight on this edge is greater than path length of
4. So there is no need to relabel this vertex 4 because we already have a path
from 0 to 4 which is of length 8 and using this 3 we get a path of length 9,
so there is no need to relabel this vertex 4. Next we take this vertex 6.
Path length of 3 plus weight on this edge is less than path length of 6, so it
will be relabeled. Now from all the temporary vertices this
vertex 1 has a minimum path length, so we’ll make it permanent.
Now this vertex 1 is our current vertex. You have to examine all the
vertices that are adjacent to vertex 1 and are temporary. There is only one
vertex adjacent to vertex 1 and it is temporary, so we’ll examine this vertex 4. Now path length of 1 plus weight on this
edge is less than path length of 4, it means that we have got a shorter path. Till now
the path from 0 to 4 was of length 8 but using this vertex 1 we’ve got a path
of length 7. So we’ll relabel this vertex 4. Now path length of this vertex 4 is
7 and predecessor is vertex 1. Now from all the temporary vertices this
vertex 4 has a minimum path length, so we’ll make this vertex 4 permanent and
now this vertex 4 is a current vertex. Vertices 5 and 7 are edges into this
vertex 4 and both of them are temporary, so we’ll examine these vertices 5 and 7.
Now both of them have path length infinity, so definitely both of them will
be relabeled. Now from all the temporary vertices this
vertex 6 has a minimum path length, so now we’ll make vertex 6 permanent
and now 6 is a current vertex. It has only one vertex adjacent to this vertex
6 and it is temporary so we’ll examine this vertex 7. Now path length of vertex 6 plus weight on
this edge is greater than path length of 7, so there is no need to relabel
this vertex 7. Now from all the temporary vertices this vertex 7 has
a minimum path length, so now we’ll make vertex 7 permanent and now this
vertex 7 is a current vertex. Now vertices adjacent to this vertex 7 are
5 & 8 and both of them are temporary, so we’ll examine these vertices 5 & 8. First we
take this vertex 5, now path length of vertex 7 plus weight on this edge is
less than path length of vertex 5. This means that we have got a shorter path.
Till now the shortest path that we knew from vertex 0 to vertex 5 was this. It
was of length 16. Now using this vertex 7, we got this path which is of length 14,
so we’ll relabel this vertex 5. Now its path length is 14 and its predecessor is
7. Now we come to this vertex 8, its path length infinity, so it will
definitely be relabeled. Now from all the temporary vertices left
this vertex 5 has the minimum path length, so we’ll make vertex 5 permanent.
Now this vertex 5 is a current vertex. Now we have only one vertex that is
adjacent to this vertex 5 and it is not temporary,
so next we’ll make vertex 8 permanent because from these two temporary
vertices left this vertex 8 has a minimum path length,
so now our current vertex is vertex 8. We have only one vertex that is adjacent to this vertex 8 and this vertex is
permanent, so there are no temporary adjacent vertices.
Now we have only one temporary vertex left and it has path length infinity. In
the previous lecture we had learnt that the algorithm stops when either there are
no temporary vertices left or all the temporary vertices that are left the
path length infinity. Now we are left with one temporary vertex and it has path
length infinity, so it is time to stop a algorithm. We had also learnt that all
the vertices that will be left with path length infinity will be those vertices
that are not reachable from the source vertex. So here this vertex 2 is the only
vertex that is not reachable from the source vertex 0. Now at the end of the algorithm the path
length and predecessor of all the vertices have been set. Now we can easily
find shortest path from vertex 0 to any other vertex by following the
predecessors till we reach the source vertex. Suppose we have to find shortest
path from vertex 0 to vertex 6, now predecessor of vertex 6 is 3 and
predecessor of vertex 3 is 0, so this is the shortest path from vertex 0 to
vertex 6. Now suppose we have to find shortest path to vertex 8. The
predecessor of vertex 8 is vertex 7, predecessor of vertex 7 is
vertex 4, predecessor of vertex 4 is vertex 1 and predecessor of vertex 1
is vertex 0, so this is the shortest path from vertex 0 to vertex 8.
In this video we’ll see the implementation of Dijkstra’s algorithm.
In this class Vertex we have taken these three additional members, status which
can be temporary or permanent, predecessor and path length.
Now in this class DirectedWeighedGraph, we have taken these four constants, these two
constants are for specifying the status of vertices, this constant NIL is used to
initialize the predecessors and this constant INFINITY is used to initialize
the path length of all the vertices. Now in this method Dijkstra() we’ll apply the
Dijkstra’s algorithm to set the predecessor and path length values of all
the vertices. We will call this method in the public method FindPaths(). Now first
let’s see how this method works. At the start of the Dijkstra’s algorithm
all vertices are temporary, path length of each vertex is infinity and
predecessor of each vertex is NIL. First we make the path length
of source vertex equal to 0. The index of the source vertex is
provided as the argument. Now in this loop, first we find the temporary
vertex with the minimum path length using this method. Let’s see this method. This method will return the temporary
vertex with minimum path length and it will return NIL if there is no temporary
vertex left or all the temporary vertices left have path length equal to infinity. Now the vertex returned by this method becomes the current vertex. If NIL is
returned by this method it means that either there is no temporary vertex left
or all temporary vertices left have path length infinity. So in that case our
algorithm finishes, so we will just return. Now if NIL is not returned then we will come here and make vertex c permanent, now
c is the current vertex. Now in this loop we check all the vertices that are
adjacent to vertex c and are temporary and we relabel all those vertices which
satisfy this condition. Now this is an infinite loop,
so this process continues till this method returns NIL. In that case we’ll
return from this method. Now we have called this method Dijkstra()
in the public method FindPaths(), so now let’s see this method FindPaths(). In this
method the name of the source vertex is sent as argument. There we find the index
of source vertex, then we call this method with the index of the source vertex.
Now after this call the predecessor and path length values of all vertices will have
been set. Now if path length of any vertex is infinity, it means that the
vertex is not reachable from the source vertex. So in that case we print this message otherwise we print the shortest path
from source vertex to vertex v using this method FindPath(). So now let’s see
this method FindPath(). This array path is used to store the path
from source vertex s to destination vertex v. This variable sd denotes the
length of the shortest path from s to v and this variable count will store the
number of vertices in that shortest path. Now here we are creating the path by
following the predecessors till we reach the source vertex and here we are displaying
the shortest path and shortest distance. Now this is the method main() where we have created the graph that we have seen in the example. We have called this method FindPaths() with
source vertex 0, now let’s run this program. Source vertex is 0 and the
shortest path and shortest distances from vertex 0 to all other vertices are displayed.

Tags: , , , , , , , , , , , , ,

10 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *