In Java please write a program that does the following Using Dijkstra\'s algorit
ID: 3739599 • Letter: I
Question
In Java please write a program that does the following
Using Dijkstra's algorithm, write a Java program to find the lengths of the shortest paths from a vertex i to all the other vertices in a undirected, connected, weighted simple graph G whose vertices are labeled from thru v? . The inputs to your program will be the number of vertices followed by the weighted adjacency matrix of a graph as well as the initial vertex number from which the shortest path lengths are to be computed. The output will be the shortest path lengths from the vertex to all the other vertices in a nice format. Input VO V2 V4 Vo 2 3 00 vi 2 0 0 570 V2 3 0 0 5 0 Va 5 0 2 V4 0 75 1 3 Vs 0 0 3 0Explanation / Answer
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source.
The Java code is as followes:
import java.util.Scanner;
import java.io.File;
import java.util.PriorityQueue;
class Data implements Comparable<Data> {
public final int index;
public final int priority;
public Data(int index, int priority) {
this.index = index;
this.priority = priority;
}
@Override
public int compareTo(Data other) {
return Integer.valueOf(priority).compareTo(other.priority);
}
public boolean equals(Data other) {
return priority == other.priority;
}
// also implement equals() and hashCode()
}
public class Dijkstra{
/* dijkstra(G,n,i,j)
Given a weighted adjacency matrix for graph G, return the length
of the shortest (i,j)-path.
For full marks, the implementation must run in O(m*log(n)) time in the worst
case on a graph with n vertices and m edges.
If G[i][j] == 0, there is no edge between vertex i and vertex j
If G[i][j] > 1, there is an edge between i and j and the value of G[i][j] is its weight.
No entry of G will be negative.
*/
static int MAX_VERTS = 50000;
static int dijkstra(int[][] G, int i, int j){
//Get the number of vertices in G
int n = G.length;
/* ... Your code here ... */
int[] distance = new int[G.length];
PriorityQueue<Data> PQ = new PriorityQueue<Data>();
boolean[] inTree = new boolean[G.length];
for (int index = 0; index < G.length; index++) {
if (index == i) {
distance[index] = 0;
}
else {
distance[index] = Integer.MAX_VALUE;
PQ.add(new Data(index,distance[index]));
inTree[index] = true;
}
}
for (int index = 0; index < G.length; index++) { // for each edge (v,z) do
if (G[i][index] != 0) { // There is an edge
if (distance[i] + G[i][index] < distance[index]) { // if D[v] + w((v,z)) < D[z] then
int oldIndex = distance[index];
distance[index] = distance[i] + G[i][index]; // D[z] ? D[v] + w((v,z))
PQ.remove(new Data(index, oldIndex));
PQ.add(new Data(index, distance[index])); // update PQ wrt D[z]
}
}
}
while (PQ.peek() != null) { // If PQ isn't empty
Data vertex = PQ.poll(); // RemoveMin
for (int index = 0; index < G.length; index++) { // for each edge (u,z) with z ? PQ do
if (G[vertex.index][index] != 0 && inTree[index] == true) { // z ? PQ
if (distance[vertex.index] + G[vertex.index][index] < distance[index]) { // if D[v] + w((v,z)) < D[z] then
int oldIndex = distance[index];
distance[index] = distance[vertex.index] + G[vertex.index][index]; // D[z] ? D[v] + w((v,z))
PQ.remove(new Data(index, oldIndex));
PQ.add(new Data(index, distance[index])); // update PQ wrt D[z]
}
}
}
}
if (distance[j] == Integer.MAX_VALUE || distance[j] < 0) {
return -1;
}
else {
return distance[j];
}
}
public static void main(String[] args){
/* Code to test your implementation */
/* You may modify this, but nothing in this function will be marked */
int graphNum = 0;
Scanner s;
if (args.length > 0){
//If a file argument was provided on the command line, read from the file
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{
//Otherwise, read from standard input
s = new Scanner(System.in);
System.out.printf("Reading input values from stdin. ");
}
//Read graphs until EOF is encountered (or an error occurs)
while(true){
graphNum++;
if(!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++){
G[i] = new int[n];
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;
}
int shortestPathLength = dijkstra(G,0,n-1);
System.out.printf("Graph %d: Length of shortest (0,n-1)-path: %d ",graphNum,shortestPathLength);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.