Dijkstra’s algorithm in java

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.

đź’» Awesome Tech Resources:
  • Looking for ⚒️ tech jobs? Go to our job portal.
  • Looking for tech events? Go to tech events 🗓️ Calendar.️

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.

Related Posts

  • 26 September

    Print all subarrays of a given array

    If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs. In this post, we will see how to print all subarrays of given array. Problem Print all print all subarrays of given array. For example: If array is {1,2,3} then you need to print {1}, […]

  • 16 September

    Doubly Linked List in java

    In this post, we will see about Doubly LinkedList implementation in java. We have already seen the implementation of singly linked list. You can consider this as an extension of Singly linked list.It is quite complex to implement it as compared to singly linked list. In doubly linked list, Node has data and pointers to […]

  • 22 October

    Trie data structure in java

    In this post, we will see about trie data structure in java. What is Trie : Trie is data structure which stores data in such a way that it can be retrieved faster and improve the performance. Some real time examples: Trie can be used to implement : Dictionary Searching contact in mobile phone book.  […]

  • 12 October

    Implement Queue using Linked List in java

    If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions. In this post , we will see how to implement Queue using Linked List in java. Queue is abstract data type which demonstrates First in first out (FIFO) behaviour. We will implement same behaviour using Array. Although java provides […]

  • 10 October

    Convert sorted array to balanced binary search tree

    In this post ,  we will see how to convert sorted array to balanced binary search tree. Algorithm: You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array or sub array will […]

  • 23 September

    Sort a Stack using another stack

    If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs. In this post,  we will see how to sort a stack using another stack. Problem Given a Stack,  you need to sort it with the help of temporary stack. Solution : Let’s say,  you have […]

Leave a Reply

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

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.