G = (V;E) is a directed graph, where n vertices and m edges. G can be represente
ID: 3915863 • Letter: G
Question
G = (V;E) is a directed graph, where n vertices and m edges. G can be represented as an adjacency matrix E, n x n, where n <= 10000. Please see Figure 1 as an example. You will read a sparse matrix E from an input file; There will be ONE matrix entry per line in the input file and each line will have a triplet of numbers i, j, length where 1 <= i, j <= n indicate the entry, length denotes the length for a directed edge pointing from vertex i to j. Given a source vertex 1 <= s <= n and a destination vertex 1 <= d <= n, your program should output the result:
1. The shortest path from s to d.
2. The longest path from s to d.
3. Total number of paths from s to d.
Input file: contains the vertices and edges, the form of the input file detailed above. All lengths are decimals and bigger than 0. All vertices are integers and bigger than 0. The file should be read sequentially. If same directed edge with different edge length, only the latter one should be kept. Path file: contains the number of source and destination vertices. The first line is the source vertex, the second line is the destination vertex. The vertices number may be invalid, if that happens, you should follow the output protocols to output specific result. Only integers will be given, you don’t need to consider the letters. Empty lines may be given.
1length 22.1 2 3 1.9 3 51.5 4 51.2 5 67.8 5 73.5 5 8 2.2 6 4 1.1 7 62.4 9 5 1.8Explanation / Answer
package datastructure;
import java.io.*;
import java.util.*;
// class GraphShortestLongestTotal definition
class GraphShortestLongestTotal
{
// Creates a final variable of type integer for maximum value
static final int INFINITE = Integer.MAX_VALUE;
// Inner class AdjListNode definition
class AdjecentListNode
{
// Instance variable to store vertices
private int ver;
// Instance variable to store weight
private int weight;
// Parameterized constructor to initialize instance variables
AdjecentListNode(int vv, int ww)
{
ver = vv;
weight = ww;
}// End of parameterized constructor
// Method to return vertices
int getVer()
{
return ver;
}// End of method
// Method to return weight
int getWeight()
{
return weight;
}// End of method
}// End of inner class
// Inner class MyGraph definition
class MyGraph
{
// To store vertices
private int Ver;
// Declares a linked list of type AdjecentListNode type array
private LinkedList<AdjecentListNode>adjcent[];
// Parameterized constructor to initialize data member
MyGraph(int ver)
{
Ver = ver;
// Dynamically allocate memory of size Ver
adjcent = new LinkedList[Ver];
// Loops to initialize each index of the adjcent array
for (int c = 0; c < ver; ++c)
adjcent[c] = new LinkedList<AdjecentListNode>();
}// End of parameterized constructor
// Method to add edge
void addEdge(int uu, int vv, int weight)
{
// Calls the parameterized constructor
AdjecentListNode node = new AdjecentListNode(vv ,weight);
// Add vv to uu's list
adjcent[uu].add(node);
}// End of method
// Recursive method used by shortestPath.
void topologicalSort(int ver, Boolean visited[], Stack myStack)
{
// Mark the current node as visited.
visited[ver] = true;
// Recur for all the vertices adjacent to this vertex
Iterator<AdjecentListNode> iterator = adjcent[ver].iterator();
while (iterator.hasNext())
{
AdjecentListNode node = iterator.next();
// Checks if not visited
if (!visited[node.getVer()])
// Recursively calls the method
topologicalSort(node.getVer(), visited, myStack);
}// End of while loop
// Push current vertex to stack which stores result
myStack.push(new Integer(ver));
}// End of method
// Method to find shortest paths from given vertex.
// Calls recursive topologicalSort() to get topological sorting of given graph.
void shortestPath(int s)
{
// Creates a Stack class object
Stack myStack = new Stack();
int dist[] = new int[Ver];
// Mark all the vertices as not visited
Boolean visitedNode[] = new Boolean[Ver];
// Loops till number of vertices and sets the visited status to false
for (int i = 0; i < Ver; i++)
visitedNode[i] = false;
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < Ver; i++)
if (visitedNode[i] == false)
topologicalSort(i, visitedNode, myStack);
// Initialize distances to all vertices as infinite and distance to source as 0
for (int i = 0; i < Ver; i++)
dist[i] = INFINITE;
dist[s] = 0;
// Process vertices in topological order
while (myStack.empty() == false)
{
// Get the next vertex from topological order
int u = (int)myStack.pop();
// Update distances of all adjacent vertices
Iterator<AdjecentListNode> iterator;
if (dist[u] != INFINITE)
{
iterator = adjcent[u].iterator();
// Loops till end of the list
while (iterator.hasNext())
{
AdjecentListNode al = iterator.next();
if (dist[al.getVer()] > dist[u] + al.getWeight())
dist[al.getVer()] = dist[u] + al.getWeight();
}// End of inner while loop
}// End of if condition
}// End of outer while loop
// Print the calculated shortest distances
for (int co = 0; co < Ver; co++)
{
// Checks if current index position is maximum value then display INF as infinite
if (dist[co] == INFINITE)
System.out.print( "INF ");
// Otherwise display the value
else
System.out.print( dist[co] + " ");
}// End of for loop
}// End of method
// Method to find longest distances from a given vertex.
// Calls recursive topologicalSortUtil() to get topological sorting.
void longestPath(int s)
{
// Creates a Stack class object
Stack myStack = new Stack();
int dist[] = new int[Ver];
// Mark all the vertices as not visited
Boolean visitedNode[] = new Boolean[Ver];
// Loops till number of vertices and set the visited status to false
for (int co = 0; co < Ver; co++)
visitedNode[co] = false;
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int co = 0; co < Ver; co++)
// Checks if the current node visited status is false
if (visitedNode[co] == false)
// Calls the method to sort
topologicalSort(co, visitedNode, myStack);
// Initialize distances to all vertices as infinite and distance to source as 0
for (int co = 0; co < Ver; co++)
dist[co] = INFINITE;
dist[s] = 0;
// Process vertices in topological order
while (myStack.empty() == false)
{
// Get the next vertex from topological order
int u = (int)myStack.pop();
// Update distances of all adjacent vertices
Iterator<AdjecentListNode> iterator;
// Checks if the current index position value is not maximum value
if (dist[u] != INFINITE)
{
iterator = adjcent[u].iterator();
// Loops till end of the list
while(iterator.hasNext())
{
AdjecentListNode al = iterator.next();
if (dist[al.getVer()] < dist[u] + al.getWeight())
dist[al.getVer()] = dist[u] + al.getWeight();
}// End of inner while loop
}// End of if condition
}// End of outer while loop
// Print the calculated longest distances
for (int co = 0; co < Ver; co++)
// Checks if the current index position data is equals to maximum value display INF as infinite
if(dist[co] == INFINITE)
System.out.print("INF ");
// Otherwise display the value
else
System.out.print(dist[co] + " ");
}// End of method
// Recursive method to count all paths from 'so' to 'de'.
int countPaths(int so, int de, boolean visitedNode[], int pathCounter)
{
// Mark the current node as visited and print it
visitedNode[so] = true;
// If current vertex is same as destination, then increment count
if (so == de)
{
// Increase the path counter by one
pathCounter++;
}// End of if condition
// Recur for all the vertices adjacent to this vertex
else
{
Iterator<AdjecentListNode> irerator = adjcent[so].listIterator();
// Loops till end of the list
while (irerator.hasNext())
{
AdjecentListNode al = irerator.next();
if (!visitedNode[al.getVer()])
{
pathCounter = countPaths(al.getVer(), de, visitedNode, pathCounter);
}// End of if condition
}// End of while loop
}// End of else
// Sets the source index position of visited array status to false
visitedNode[so] = false;
// Returns the path counter
return pathCounter;
}// End of method
// Method returns count of paths from 'so' to 'de'
int countPaths(int so, int de)
{
// Mark all the vertices as not visited
boolean visitedNode[] = new boolean[Ver];
Arrays.fill(visitedNode, false);
// Call the recursive method to count all paths
int pathCounter = 0;
// Calls the method to count the path
pathCounter = countPaths(so, de, visitedNode, pathCounter);
return pathCounter;
}// End of method
}// End of inner class
// Method to create a new graph instance through an object of ShortestPath class.
MyGraph newGraph(int number)
{
return new MyGraph(number);
}// End of method
// main method definition
public static void main(String args[])
{
// Creates an object of class GraphShortestLongestTotal
GraphShortestLongestTotal gt = new GraphShortestLongestTotal();
// Creates an object of the class MyGraph with parameterized constructor for 6 vertices
MyGraph graph = gt.newGraph(6);
// Calls the method to add the edges
graph.addEdge(0, 1, 5);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 3, 6);
graph.addEdge(1, 2, 2);
graph.addEdge(2, 4, 4);
graph.addEdge(2, 5, 2);
graph.addEdge(2, 3, 7);
graph.addEdge(3, 4, -1);
graph.addEdge(4, 5, -2);
int source = 1, destination = 3;
// Calls the method to display the shortest path
System.out.println("Following are shortest distances from source " + source);
graph.shortestPath(source);
System.out.println(" Following are longest distances from source vertex " + source);
// Calls the method to display the longest path
graph.longestPath(source);
// Calls the method to display the count path
System.out.println(" Count Path " + graph.countPaths(source, destination));
}// End of main method
}// End of class
Sample Output:
Following are shortest distances from source 1
INF 0 2 6 5 3 Following are longest distances from source vertex 1
INF 0 INF INF INF INF
Count Path 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.