Shortest Path (DAG) Students, In this coding assignment, you will be asked to wr
ID: 3667533 • Letter: S
Question
Shortest Path (DAG) Students, In this coding assignment, you will be asked to write Java code to read a text file (input.txt) of a graph represented as an adjacency list. Example: A, 7, B, 9, C B, 1, C C, 8, E, 2, F D, 1, E, 3, G E, 3, G F, 3, D, -3, H H, 6, G K, 3, H, -1, F The graph represented by the adjacency list above looks like this: The graph is a Directed Acyclic Graph (no cycles). You are required to write Java code to find one correct topological sorting for the graph; and after that, you will ask the user for a node (starting node), then you will print the shortest path from that node to all other (following nodes) Example, after reading the adjacency list above, if the user enters the value 'A' as the starting node, then your program should print the following: B: A - B (7) \ Essentially, this means that the shortest path from A to B is A - B and its length is 7 C: A - B - C (8) \ Essentially, this means that the shortest path from A to C is A - B - C and its length is 8 D ... \ You will have to list all the shortest paths from A to all other nodes E ... F ... ... Your implementation of the topological sort should be efficient
Explanation / Answer
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author HARE KRISHNA
*/
import java.io.*;
import java.util.*;
class ToplogicalSortDag {
private int V; // No. of vertices
private LinkedList<Integer> adj[]; // Adjacency List
//Constructor
ToplogicalSortDag(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the ToplogicalSortDag
void addEdge(int v,int w) { adj[v].add(w); }
// A recursive function used by topologicalSort
void topologicalSortUtil(int v, Boolean visited[],Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
// Push current vertex to stack which stores result
stack.push(new Integer(v));
}
// The function to do Topological Sort. It uses recursive
// topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();
// Mark all the vertices as not visited
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}
}
//Main Class
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author HARE KRISHNA
*/
class DagMain {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
// Create a ToplogicalSortDag given in the above diagram
ToplogicalSortDag g = new ToplogicalSortDag(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological " +
"sort of the given ToplogicalSortDag");
g.topologicalSort();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.