I need to come up with Dijstrak\'s ShortestPath Algorithm in this method (in Jav

Question

I need to come up with Dijstrak's ShortestPath Algorithm in this method (in Java):

public Shortest_Path_Info[] shortest_Path(String label){...

I need to use a minBinHeap and a queue. There is an edge class, as well as a node class (vertices class), the node class contains what you would expect as well as HashMaps containing the incoming and outgoing vertices, to be used for looking at the adjacent nodes:

HashMap<String, Edge> adjListIn = new HashMap<String, Edge>();

HashMap<String, Edge> adjListOut= new HashMap<String, Edge>();

The Shortest_Path_Info class just contains:

private String destination;
private long weight;

and the appropriate constructor to set these values, as well as getters and setters.

Basically I need to write the method to implement Djikstra's Algorithm and return an array of these Shortest_Path_Info objects.

Thank you

Explanation / Answer

Please see the namings, else the code is fine.

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s , there is generation of a shortest path tree with given source as root. Two sets are maintained, one set contains vertices included in shortest path tree and second set includes vertices not yet included in shortest path tree. At each step user finds a vertex which is in the other set and has minimum distance from source.

Algorithm
1) Create a set shortest path tree set that tracks the vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While set shortest path tree set doesn’t include all vertices

a) Pick a vertex u which is not there in set shortest path tree set and has minimum distance value.

b) Include u to set shortest path tree set.

c) Update distance value of all adjacent vertices of u.

To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Code:

import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class DijkstraPriorityQueue
{
private int distances[];
private Set<Integer> settled;
private PriorityQueue<Node> priorityQueue;
private int number_of_nodes;
private int adjacencyMatrix[][];

public DijkstraPriorityQueue(int number_of_nodes)
{
this.number_of_nodes = number_of_nodes;
distances = new int[number_of_nodes + 1];
settled = new HashSet<Integer>();
priorityQueue = new PriorityQueue<Node>(number_of_nodes,new Node());
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
}

public void dijkstra_algorithm(int adjacency_matrix[][], int source)
{
int evaluationNode;
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacencyMatrix[i][j] = adjacency_matrix[i][j];

for (int i = 1; i <= number_of_nodes; i++)
{
distances[i] = Integer.MAX_VALUE;
}

priorityQueue.add(new Node(source, 0));
distances[source] = 0;
while (!priorityQueue.isEmpty())
{
evaluationNode = getNodeWithMinimumDistanceFromPriorityQueue();
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}

private int getNodeWithMinimumDistanceFromPriorityQueue()
{
int node = priorityQueue.remove();
return node;
}

private void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;

for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if (!settled.contains(destinationNode))
{
if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;
}
priorityQueue.add(new Node(destinationNode,distances[destinationNode]));
}   
}
}
}

public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int source = 0;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++)
{
    for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
       if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = Integer.MAX_VALUE;
}
}
}

System.out.println("Enter the source ");
source = scan.nextInt();

DijkstraPriorityQueue dijkstrasPriorityQueue = new DijkstraPriorityQueue(number_of_vertices);
dijkstrasPriorityQueue.dijkstra_algorithm(adjacency_matrix, source);

System.out.println("The Shorted Path to all nodes are ");
for (int i = 1; i <= dijkstrasPriorityQueue.distances.length - 1; i++)
{
System.out.println(source + " to " + i + " is " + dijkstrasPriorityQueue.distances[i]);
}
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}  
}
class Node implements Comparator<Node>
{
public int node;
public int cost;

public Node()
{
}

public Node(int node, int cost)
{
this.node = node;
this.cost = cost;
}

@Override
public int compare(Node node1, Node node2)
{
if (node1.cost < node2.cost)
return -1;
if (node1.cost > node2.cost)
return 1;
return 0;
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.