Question:
Write a Java program that implements Dijkstra's algorithm to find shortest paths to all vertices in a directed weighted graph from a given starting vertex.
As mentioned in the lectures, choosing an implementation for the data structure representing a graph is highly dependent on the sparsity of the graph. For dense graphs, an adjacency matrix representation is preferable, but for sparse graphs, an adjacency list representation may be more efficient. You are asked to implement either the adjacency list or adjacency matrix representation for graphs in your program. If you choose to extend you implementation from Lab03 then it will need account for weighted edges.
Answer:
How Code works:
- GraphShortesPath starts the program and call GraphBuilder with fileName to read the graph using JDOM library.
- GraphBuilder will make a 2D adjacency matrix after reading all the graph data and pass this matrix to one of our three classes.i.e. Graph_List.java, Graph_Priority_Queue.java or Graph_My_Priority_Queue.java
- Then we call shortestpath method of one of these three classes to find the shortest path from source to all other nodes. We are doing this by using Dijkstra's Algorithm.
- We are using java.util.ArrayList , java.util.Priority Queue and Our own implementation of priority Queue in these three classes in Dijkstra's algorithm as Dijkstra's algorithm is a greedy algorithm and it needs to find the node with lowest distance at each step.
Choice of Data Structure for Priority Queue Implementation :
- We have implemented our own priority Queue using Min Heap. Min Heap is a special type of tree structure which has a special property. The root of a Min Heap is larger then its child at each levels. It may be the level1 or Level2 or any other level.
- While even doing insertions and deletions also thsi property is maintained.
- Time complexity of Min Heap is
table shows indexes of other nodes for the ith node, i.e., Arr[i]:
|
Arr[(i-1)/2]
|
Returns the parent node
|
|
Arr[(2*i)+1]
|
Returns the left child node
|
|
Arr[(2*i)+2]
|
Returns the right child node
|
Time Complexity for Removal : O(LogN) as tree structure is also maintained at each removal.
Time Complexity for Insertion : O(LogN) as tree structure is also maintained at each insertion.
Space Complexity : O(n) as the elements are stored in an array and we will need atleast an array of size equal to the number of elements to be stored in array.
