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<Edge>[] 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 < nodes; i++) {
if (i == start)
continue;

if (shortDist[i] != INFINITY) {
sum += shortDist[i];
}
}

System.out.println();
System.out.println("Sum is:"+sum);

} catch (IOException e) {
//
}
Date d1 = new Date();
long s2 = d1.getTime();
System.out.println((s2 - s1) / 100);
}

static void constructGraph(Scanner sc) {
adjList = new ArrayList[nodes];

for (int i = 0; i < nodes; i++)
adjList[i] = new ArrayList<>();

for (int i = 0; i < nodes && sc.hasNext(); i++) {
String edge;
String n = sc.nextLine();
while (sc.hasNext() && !(edge = sc.nextLine()).isEmpty()) {
String[] e = edge.trim().split(" ");
int from, to, weight;

to = Integer.parseInt(e[0]);
weight = Integer.parseInt(e[1].trim());
adjList[Integer.parseInt(n)].add(new Edge(to, weight));
adjList[to].add(new Edge(Integer.parseInt(n), weight));
}
}
}

static void calShortestPaths(int start) {
shortDist = new int[nodes];

for (int i = 0; i < nodes; i++)
shortDist[i] = INFINITY;

TreeSet<Node> set = new TreeSet<>();

shortDist[start] = 0;
set.add(new Node(start, 0, -1));

while (set.size() > 0) {
Node curr = set.pollFirst();

for (Edge edge : adjList[curr.node]) {
if (shortDist[curr.node] + edge.weight < shortDist[edge.to]) {
set.remove(new Node(edge.to, shortDist[edge.to], -1));
shortDist[edge.to] = shortDist[curr.node] + edge.weight;
set.add(new Node(edge.to, shortDist[edge.to], curr.node));
}
}
}
}

private static class Edge {
int to, weight;

public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}

}

static class Node implements Comparable<Node> {
int node, dist, parent;

public Node(int node, int dist, int parent) {
this.node = node;
this.dist = dist;
this.parent = parent;
}

@Override
public int compareTo(Node o) {
if (dist == o.dist)
return Integer.compare(node, o.node);

return Integer.compare(dist, o.dist);
}

}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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