# Dijkstra's algm

vineesh mohan
Dijkstra's algm
1 Answer(s)      5 years and 5 months ago
Posted in : Java Beginners

sample program for dijkstra's algorithm????????

March 16, 2012 at 4:53 PM

```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>();

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;

}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target){
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)

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);
}

}
}
```