February 01, 2012

Dijkstra algorithm implementation in java.

Dijkstra algorithm implementation in java.




public class DijkstraAlgorithm {
public static void computePaths(Vertex source) {
source.minDistance = 0.;
PriorityQueue vertexQueue = new PriorityQueue();
vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();// Visit each edge exiting u
for (Edge e : u.adjacencies) {
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;
vertexQueue.add(v);
}}}}

public static List getShortestPathTo(Vertex target) {
List path = new ArrayList();
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("a");
Vertex v1 = new Vertex("b");
Vertex v2 = new Vertex("c");
Vertex v3 = new Vertex("d");
Vertex v4 = new Vertex("e");

Vertex []vertices= new Vertex[5];
Edge []ed=new Edge[4];

for(int i=0;i<5;i++)
{
vertices[i]= new Vertex("a"+i);
for(int j=0;j<5;j++)
{
ed[j]=new Edge(vertices[j],10+j);
}
//vertices[i].adjacencies =new Edge[]{ed[]};
}

System.out.println(vertices.length +"and "+vertices[3]);
//v0.adjacencies = new Edge[] { new Edge(v1, 8), new Edge(v2, 10),
//new Edge(v3, 8) };
//v1.adjacencies = new Edge[] { new Edge(v0, 5), new Edge(v2, 3),
//new Edge(v4, 7) };
//v2.adjacencies = new Edge[] { new Edge(v0, 10), new Edge(v1, 3) };
//v3.adjacencies = new Edge[] { new Edge(v0, 8), new Edge(v4, 12) };
//v4.adjacencies = new Edge[] { new Edge(v1, 7), new Edge(v3, 2) };
//Vertex[] vertices = { v0, v1, v2, v3, v4 };
computePaths(vertices[0]);
for (Vertex v : vertices) {
System.out.println("Distance to the vertex ( " + v + ") is : " + v.minDistance);
List path = getShortestPathTo(v);
System.out.println("Shortest path: " + path);
System.out.println(" Dijkstra algorithm to compute shortest distance ");
}}}

Please make necessary modification to run this code

Router simulator : you can create upto 10 routers, software that shows the working of a router, how shortest path is computed, calculating routing table, comparing 5 algorithms,

You can download Router simulator (Dijkstra algorithm implemented) running jar file from the below link

Server1

File name :  javabelazy35744
password : AppleIphone

Facebook comments