Quick guide about how to implement dijkstra's algorithm in java with example.

Let’s find out when to use Dijkstra’s algorithm and how it can be applied to the real-time problems.

Well, we all know that Graph is a data structure in a programming language. which has Nodes or vertices and each node is connected to other node by an edge OR Path having specific weight. Graph can have self-loop too unlike Trees.(Refer my previous post to find out the differences between Tree and Graph).

There are mainly two type of Graphs,

•         Directed Graphs.
•         Undirected Graphs.

Directed Graph

Undirected Graph.

Problem Statement:

Person X wants to travel from location-A to location-B and there are multiple paths by which these two locations are connected. Each path has different distances and so as the time. but person X is running out of time and he must follow the route with the least cost to reach destination as early as possible. To Make above problem statement simple let’s assume that, parameters like traffic and no. of signals in all the routes are the same and only differing parameter is the distance.

Solution:

Above problem can be studied as a Graph shown below, where source node is ‘0’ and destination be ‘4’.

Figure-1.

There are multiple routes exists between Node 0 to 4, Like {0-7-6-5-4}, {0-1-2-3-4},{0-1-2-5-4} and so on..

Let’s see how Dijkstra’s algorithm can help here to find out the shortest path among the all others and I also recommend that before referring to my code below, give a try by yourself in your favorite IDE 😊.

Below is the implementation using JAVA.

package com.mayank4java.algorithms;

public class DijkstraGraph {
private boolean[] isVisited;
private int[][] graph;
private int[] distance;
private int maxVal = Integer.MAX_VALUE;
private boolean flag=true;
public DijkstraGraph() {
}
public DijkstraGraph(int noOfNodes) {
isVisited = new boolean[noOfNodes];
graph = new int[noOfNodes][noOfNodes];
distance=new int[noOfNodes];
for (int i = 0; i < noOfNodes; i++) {
distance[i] = maxVal;
}
}
public void addLink(int sourceNode, int destNode, int weight) {
graph[sourceNode][destNode] = weight;
graph[destNode][sourceNode] = weight;
}
public void findShortestPath(int sourceNode)
{
int min=maxVal;
isVisited[sourceNode]=true;
if(flag)
{
distance[sourceNode]=0;/*only once */
flag=false;
}
int[] row=graph[sourceNode];
for (int i = 0; i < row.length; i++) {

if(row[i]!=0 && !(isVisited[i]) && (row[i]+distance[sourceNode]) < distance[i])
{
distance[i]=distance[sourceNode]+row[i];
}
}
min=findMin(distance,sourceNode);
if(min != maxVal)
findShortestPath(min);
}
public void printArray(int array[])
{
for (int i = 0; i < array.length; i++) {
System.out.println("Node "+i+" - Weight "+array[i]);
}
}
public int findMin(int[] array,int srcNd)
{
int minVal=maxVal;
int minIndex=maxVal;
int row[]=graph[srcNd];
for (int i = 0; i < array.length; i++) {
if(array[i] < minVal && !(isVisited[i]) && row[i] !=0)
{
minVal=array[i];
minIndex=i;
}
}
return minIndex;
}

public static void main(String[] args) {
DijkstraGraph graph = new DijkstraGraph(10);
graph.addLink(0, 1, 4);
graph.addLink(0, 7, 8);
graph.addLink(7, 1, 11);
graph.addLink(1, 2, 8);
graph.addLink(7, 8, 7);
graph.addLink(7, 6, 1);
graph.addLink(2, 8, 2);
graph.addLink(8, 6, 6);
graph.addLink(6, 5, 2);
graph.addLink(2, 5, 4);
graph.addLink(2, 3, 7);
graph.addLink(3, 5, 14);
graph.addLink(3, 4, 9);
graph.addLink(5, 4, 10);
graph.addLink(4, 9, 6);
graph.findShortestPath(0);
graph.printArray(graph.distance);
}
}

That is it folks! 😊

Hope this post helped you.Also don't forget to share and leave your comments below.