Simulate the DAG Single Source Shortest Path algorithm on the graph below, using
ID: 3577251 • Letter: S
Question
Simulate the DAG Single Source Shortest Path algorithm on the graph below, using vertex
Simulate the DAG Single Source Shortest Path algorithm on the graph below, using vertex s as a source. Use the non-DFS topological sort algorithm. Assume that initially, vertices are traversed alphabetically, and that within a vertex, its edge list is also traversed alphabetically. The graph is given as a list of outgoing edges for each vertex., including the Queue, and all intermediate distances the algorithm temporarily stores. The graph is given in adjacency matrix format, with weights. (Blank means no edge.) Show work.Explanation / Answer
import java.util.InputMismatchException;
import java.util.Scanner;
public class SingleSourceShortestPath
{
private boolean settled[];
private boolean unsettled[];
private int distances[];
private int adjMatrix[][];
private int numOfVertices;
public SingleSourceShortestPath(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 SingleSourceShortestPath(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();
SingleSourceShortestPath dijkstrasAlgorithm = new SingleSourceShortestPath(number_of_vertices);
dijkstrasAlgorithm.SingleSourceShortestPath(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();
}
}