import java.io.*;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.ArrayList;
class Vertex implements Comparable {
public int key;
public ArrayList edges;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex(int key) {
this.key = key;
edges = new ArrayList();
}
public int compareTo(Vertex other) {
return Double.compare(minDistance, other.minDistance);
}
}
class Edge {
public Vertex target;
public double weight;
public Edge(Vertex t, double w) {
target = t;
weight = w;
}
}
public class Dijkstra {
public static void shortestPath(Vertex source) {
source.minDistance = 0.0;
PriorityQueue vertexQueue = new PriorityQueue();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
for (Edge e : u.edges) {
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
vertexQueue.add(v);
}
}
}
}
public static void main(String[] args) {
HashMap nodes = new HashMap();
try {
BufferedReader br = new BufferedReader(new FileReader("data/DijkstraData.txt"));
String line = null;
while ((line = br.readLine()) != null) {
String[] arr = line.split("\t");
Vertex v;
int key = Integer.parseInt(arr[0]);
if (nodes.containsKey(key)) {
v = nodes.get(key);
} else {
v = new Vertex(key);
nodes.put(key, v);
}
for (int i = 1; i < arr.length; i++) {
String[] tmp = arr[i].split(",");
key = Integer.parseInt(tmp[0]);
Vertex ve;
if (nodes.containsKey(key)) {
ve = nodes.get(key);
} else {
ve = new Vertex(key);
nodes.put(key, ve);
}
Edge edge = new Edge(ve, Double.parseDouble(tmp[1]));
v.edges.add(edge);
}
}
} catch (IOException ex) {
ex.printStackTrace();
}
// Find shortest path from node 1 to other nodes
shortestPath(nodes.get(1));
}
}