Dijsktra’s Algorithm in Java

Dijkstra’s shortest path algorithm is used to find the shortest path in a positive weighted graph from a given source to all the other nodes. There are 3 main steps of the algorithm.

 Initialization of single source – Inserting elements into required data structures and initialization
Extract Minimum – Extracting the node with the minimum value.

Generally the vertices in the graph can be stored 3 data structures: 1. Linear Array 2. Binary Heap/Priority Queue 3. Fibonacci Heap. Depending on the data structure we use the run time complexity of the algorithm differs.

Decrease key -  includes relaxation.

Dijkstra.java

Vertex.java

Edge.java