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.

No comments:

Post a Comment