Finish the ShortestPath function implementing algorithm to compute the shortest
ID: 3779944 • Letter: F
Question
Finish the ShortestPath function implementing algorithm to compute the shortest (i.e. lowest weight) path between two vertices of an edge-weighted graph. Must implement Dijkstra’s algorithm and use a heap-based priority queue to select the nest vertex at each step (It is not necessary to store a specific minimum weight path, only to determine the total weight of such a path). A Java template has been provided containing an empty method ShortestPath, which takes a single argument consisting of a weighted adjacency matrix for an edge -weighted graph G. The expected behavior of the method is as follows: The input format used by the testing code in main consists of the number of vertices nfollowed by the n × n weighted adjacency matrix.
Input: An n×n array G representing an edge-weighted graph.
Output: An integer value corresponding to the total weight of a minimum weight path from vertex 0 to vertex 1.
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
import java.io.File;
public class ShortestPath{
/* ShortestPath(G)
Given an adjacency matrix for graph G, return the total weight
of a minimum weight path from vertex 0 to vertex 1.
If G[i][j] == 0, there is no edge between vertex i and vertex j
If G[i][j] > 0, there is an edge between vertices i and j, and the
value of G[i][j] gives the weight of the edge.
No entries of G will be negative.
*/
static int ShortestPath(int[][] G){
int numVerts = G.length;
int totalWeight = 0;
/* ... Your code here ... */
return totalWeight;
}
public static void main(String[] args){
Scanner s;
if (args.length > 0){
try{
s = new Scanner(new File(args[0]));
} catch(java.io.FileNotFoundException e){
System.out.printf("Unable to open %s ",args[0]);
return;
}
System.out.printf("Reading input values from %s. ",args[0]);
}else{
s = new Scanner(System.in);
System.out.printf("Reading input values from stdin. ");
}
int graphNum = 0;
double totalTimeSeconds = 0;
//Read graphs until EOF is encountered (or an error occurs)
while(true){
graphNum++;
if(graphNum != 1 && !s.hasNextInt())
break;
System.out.printf("Reading graph %d ",graphNum);
int n = s.nextInt();
int[][] G = new int[n][n];
int valuesRead = 0;
for (int i = 0; i < n && s.hasNextInt(); i++){
for (int j = 0; j < n && s.hasNextInt(); j++){
G[i][j] = s.nextInt();
valuesRead++;
}
}
if (valuesRead < n*n){
System.out.printf("Adjacency matrix for graph %d contains too few values. ",graphNum);
break;
}
long startTime = System.currentTimeMillis();
int totalWeight = ShortestPath(G);
long endTime = System.currentTimeMillis();
totalTimeSeconds += (endTime-startTime)/1000.0;
System.out.printf("Graph %d: Minimum weight of a 0-1 path is %d ",graphNum,totalWeight);
}
graphNum--;
System.out.printf("Processed %d graph%s. Average Time (seconds): %.2f ",graphNum,(graphNum != 1)?"s":"",(graphNum>0)?totalTimeSeconds/graphNum:0);
}
}
Explanation / Answer
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
import java.io.File;
public class ShortestPath{
/* ShortestPath(G)
Given an adjacency matrix for graph G, return the total weight
of a minimum weight path from vertex 0 to vertex 1.
If G[i][j] == 0, there is no edge between vertex i and vertex j
If G[i][j] > 0, there is an edge between vertices i and j, and the
value of G[i][j] gives the weight of the edge.
No entries of G will be negative.
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.