# 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.

Could you please share the source code of the algorithm, for this video and linked list video? Thanks.

can you please tell what is the code to find adjacency of vertex

i am trying to see the rest of implementation by adding this code STUDENT25 but it doesn't work

someone please share code for IsAdjacent() method

can you please provide the code for directedgraphmethod

plz give us the code source

Hi. Write in comments what more you want to learn. We will be happy to provide more on Data Structures and Algorithms, Advanced Programming, Object

Oriented Design.

Error isAdjacent() could not found, please share the Entire code

Nicely explained. Pls provide more on algorithms.

Want to learn Python from a wonderful python course

Enroll here – https://www.udemy.com/course/python-programming-in-depth/?couponCode=YOUTUBE10