sample program for dijkstra's algorithm????????
import java.util.*;
class Vertex implements Comparable<Vertex>{
public final String st;
public Edge[] edges;
public double distance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { st = argName; }
public String toString() { return st; }
public int compareTo(Vertex other) {
return Double.compare(distance, other.distance);
}
}
class Edge {
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight){
target = argTarget; weight = argWeight;
}
}
public class DijkastraAlgorithm{
public static void computePaths(Vertex source){
source.distance = 0;
PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
queue.add(source);
while (!queue.isEmpty()) {
Vertex vx = queue.poll();
for (Edge e : vx.edges){
Vertex v = e.target;
double weight = e.weight;
double distanceTo = vx.distance + weight;
if (distanceTo < v.distance) {
queue.remove(v);
v.distance = distanceTo ;
v.previous = vx;
queue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target){
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args){
Vertex v0 = new Vertex("Delhi");
Vertex v1 = new Vertex("A");
Vertex v2 = new Vertex("B");
Vertex v3 = new Vertex("C");
Vertex v4= new Vertex("D");
Vertex v5 = new Vertex("E");
Vertex v6 = new Vertex("F");
v0.edges = new Edge[]{ new Edge(v1, 80),
new Edge(v5, 81) };
v1.edges = new Edge[]{ new Edge(v0, 80),
new Edge(v2, 40),
new Edge(v3, 100) };
v2.edges = new Edge[]{ new Edge(v1, 40) };
v3.edges = new Edge[]{ new Edge(v1, 103),
new Edge(v5, 61),
new Edge(v6, 97) };
v4.edges = new Edge[]{ new Edge(v5, 133) };
v5.edges = new Edge[]{ new Edge(v0, 88),
new Edge(v3, 62),
new Edge(v4, 134),
new Edge(v6, 92) };
v6.edges = new Edge[]{ new Edge(v3, 97),
new Edge(v5, 88) };
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6};
computePaths(v0);
for (Vertex v : vertices){
System.out.println("Distance to " + v + ": " + v.distance);
List<Vertex> path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}
}