Dijkstra's algm

Ads

 
 
 

Share on Google+Share on Google+

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

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

Ads
View Answers

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









Related Tutorials/Questions & Answers:
Dijkstra's algm
Dijkstra's algm  sample program for dijkstra's algorithm????????   import java.util.*; class Vertex implements Comparable<Vertex>{ public final String st; public Edge[] edges; public double
Dijkstra's algm
Dijkstra's algm  sample program for dijkstra's algorithm????????   import java.util.*; class Vertex implements Comparable<Vertex>{ public final String st; public Edge[] edges; public double
Advertisements
Dijkstra's algm
Dijkstra's algm  sample program for dijkstra's algorithm????????   import java.util.*; class Vertex implements Comparable<Vertex>{ public final String st; public Edge[] edges; public double
web service
web service  hello :) if any body have an idea that can help me I would be grateful :):) So i want to creat a web service that display the bus that has the shortest path. i have a dijkstra java class and i have a data base
Tutorials   
Java Spring Hibernate Struts Training java.lang.NoClassDefFoundError: org/apache/http/client/HttpClient How do I resolve this Java Class not found exception? httpclient java.lang.NoClassDefFoundError Apache Commons ioutils maven dependency Read/Convert an inputStream to a String What is the meaning of Java Platform? Why Java is a platform independent language? What is the benefits of learning Core Java? Which technology should I learn after Java? What is array in java with example? How to Convert ArrayList to Array? How to substring in Java? How to format number in Java? What is instance variable in Java? How to download MySQL JDBC driver? What is Calendar class in Java? Which is the best Java tutorials for beginners? How to rename a file in Java? How to delete file in Java code? How to get day from date in Java using Calendar? How to get day of week in Java? How to calculate Date Difference in Java? How to compare date in Java? How to declare array in Java? How to calculate average of array in Java? What is Array in Java? write a java program to find the summation of all the integers entered on command line Sum of two numbers using command line arguments in Java How to create and use Array in Java? How to pass command line arguments in Java? How to create Applet Hello World? Appending String efficiently in Java How to append String in Java? How to list even numbers between 1 and 100? How to add BigDecimal in Java? What is Abstraction In Java? Which is best Beginners Java Tutorial? What is java.util package? Create list from array in Java Filter collection in Java 8 What is the best way to filter a Java Collection? Easy way to transform Collection to Array? How to convert Collection to Array in Java? What are Basic Java Language Elements? Advanced Java Tutorials in 2017 Java brief history Best Reasons to learn Java Java Example Codes and Tutorials in 2017 How do I read a large file quickly in Java? Is learning Java worthwhile?

Ads

 
Advertisement null

Ads