Dijkstra’s algorithm in java

Previous

In this post, we will see Dijkstra algorithm for find shortest path from source to all other vertices.

Problem

You will be given graph with weight for each edge,source vertex and you need to find minimum distance from source vertex to rest of the vertices.

Algorithm

There will be two core classes, we are going to use for Dijkstra algorithm.
Vertex: This class contains name, visited flag, predecessor(To track the short path, so that we can backtrack) and distance from source node and also the list of outgoing edge from this vertex.
Edge: This class contains Source vertex, target vertex, and weight.

Let’s first understand how are we going to solve it visually.

DijkstraInitialize

As you can see, we have initialized predecessor and minimum distance to default.Green node represents visited nodes and red color represent neighbors of the vertex.

Dijkstra2

Dijkstra3

Here we are considering :

Total distance from source vertex A to vertex B via vertex C: 15

Total distance from source vertex A to vertex D via vertex C: 19

Total distance from source vertex A to vertex E via vertex C: 21

As distance from C to B is minimum i.e 15, that’s why we have chosen vertex B as next vertex.

Dijkstra4

Dijkstra6

As you can see, we are done with Dijkstra algorithm and got minimum distances from Source Vertex A to rest of the vertices.

Let me go through core algorithm for Dijkstra.

  • Set distance for source Vertex to 0.
  • Set distance for all other vertices to infinity.
  • At each vertex, we need to choose a node with minimum distance from source vertex and we are going to use priority queue for that.
  • Add source node to PriorityQueue.
  • Do the following when PriorityQueue is not empty
    • Poll vertex (Let’ say vertex A) from the PriorityQueue.
    • Iterate over neighbours(Let’s say Vertex B) for the vertex A.
    • Calculate new distance for vertex B by adding vertex.getDistance and edge.getWeight
    • If new distance <  Vertex B’s current distance then update the node(Distance,predecessor) in PriorityQueue.

Let’s see complete source code for Dijkstra’s algorithm

Dijkstra’s algorithm example

Create a class named Vertex.java as below:

Create another class named Edge.java as below.

Create another class named “DijkstraShortestPath.java” as below. This will contain main Dijkstra algorithm.

Create another class named “DijkstraMain.java”. This class will contain main function to run the algorithm.

When you run above program, you will get below output:

======================================
Calculating minimum distance
======================================
Minimum distance from A to B: 15.0
Minimum distance from A to C: 10.0
Minimum distance from A to D: 16.0
Minimum distance from A to E: 21.0
===================== =================
Calculating Paths
======================================
Shortest Path from A to B: [A, C, B]
Shortest Path from A to C: [A, C]
Shortest Path from A to D: [A, C, B, D]
Shortest Path from A to E: [A, C, E]

That’s all about Dijkstra algorithm in java.

Previous

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.

Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog