You want to code Dijkstra\'s Single Source Shortest Path algorithm, You want to

Question

You want to code Dijkstra's Single Source Shortest Path algorithm,

You want to code Dijkstra's Single Source Shortest Path algorithm, using a min in-heap to store path lengths. As discussed in class, you also want to extend it to work on graphs with negative edge weights, for those graph instances where it happens to work correctly. Thinking back to our heap lab, where is the natural check to see if something has gone wrong (that is, when would it be easiest to recognize that it is not working)? Specifically, how would you change your code to check for this, assuming that you had code which worked efficiently? (Assume that you have used your heap code with a graph vertex, rather than the "Student" class we used in the lab.)

Explanation / Answer

import java.util.InputMismatchException;
import java.util.Scanner;

public class DisjkstraShortestPath
{
private boolean settled[];
private boolean unsettled[];
private int distances[];
private int adjMatrix[][];
private int numOfVertices;

public DisjkstraShortestPath(int numOfVertices)
{
this.numOfVertices = numOfVertices;
this.settled = new boolean[numOfVertices + 1];
this.unsettled = new boolean[numOfVertices + 1];
this.distances = new int[numOfVertices + 1];
this.adjMatrix = new int[numOfVertices + 1][numOfVertices + 1];
}

public void DisjkstraShortestPath(int source, int adjMatrix[][])
{
int evaluationnode;
for (int vertex = 1; vertex <= numOfVertices; vertex++)
{
distances[vertex] = Integer.MAX_VALUE;
}

for (int sourcevertex = 1; sourcevertex <= numOfVertices; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= numOfVertices; destinationvertex++)
{
this.adjMatrix[sourcevertex][destinationvertex]
= adjMatrix[sourcevertex][destinationvertex];            
}
}

unsettled[source] = true;
distances[source] = 0;
while (getUnsettledCount(unsettled) != 0)
{
evaluationnode = getNodeWithMinimumDistanceFromUnsettled(unsettled);
unsettled[evaluationnode] = false;
settled[evaluationnode] = true;
evaluateNeighbours(evaluationnode);
}
}

public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int vertex = 1; vertex <= numOfVertices; vertex++)
{
if (unsettled[vertex] == true)
{
count++;
}
}
return count;
}

public int getNodeWithMinimumDistanceFromUnsettled(boolean unsettled[])
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numOfVertices; vertex++)
{
if (unsettled[vertex] == true && distances[vertex] < min)
{
node = vertex;
min = distances[vertex];
}
}
return node;
}

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

for (int destinationNode = 1; destinationNode <= numOfVertices; destinationNode++)
{
if (settled[destinationNode] == false)
{
if (adjMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;  
}
unsettled[destinationNode] = true;
}
}
}
}

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();

DisjkstraShortestPath dijkstrasAlgorithm = new DisjkstraShortestPath(number_of_vertices);
dijkstrasAlgorithm.DisjkstraShortestPath(source, adjacency_matrix);

System.out.println("The Shorted Path to all nodes are ");
for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)
{
System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);
   }
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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