Java: Implement DIJKSTRA\'s algorithm for Single Source Shortest Path Problem wi

Question

 Java: Implement DIJKSTRA's algorithm for Single Source Shortest Path Problem with BINARY Heaps. The running time should be O(ElogV)  Your program should read data from file (see samples below) and output a single number = sum of lengths of the shortest paths from node 0 to each node.  INPUT FORMAT: The first line of each file below contains the number of vertices and the number of edges in the graph (in the format "n=XXXX m=XXXXX"). The rest of the file is organized as follows:  each vertex i appears on a line by itself, followed by a line for each neighbor j>i of i (containing j and the length of edge (i,j)). Each list of neighbors is ended by an empty line. Vertices i which do not have neighbors with an index greater than i are not represented.  NOTE: Vertices are indexed from 0 to n-1.  NOTE: each edge is mentioned only once with its smaller number endpoint   the length of the shortest path tree should be 625349.  Program should give output in less than 1 second. 

 SAMPLE INPUT:  

 https://grid.cs.gsu.edu/~cscazz/CS4520/1000.txt 

Explanation / Answer

import java.io.File; import java.io.IOException; import java.util.*; public class Dijkstra { static final int INFINITY = Integer.MAX_VALUE; static int nodes, edges; static int[] shortDist; static List[] adjList; public static void main(String[] args) { Date d = new Date(); long s1 = d.getTime(); try { Scanner sc = new Scanner(new File("test.txt")); String line = sc.nextLine(); String[] ne = line.split(" "); nodes = Integer.parseInt(ne[0].split("=")[1]); edges = Integer.parseInt(ne[1].split("=")[1]); constructGraph(sc); int start = 0; calShortestPaths(start); int sum = 0; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.