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