Share on Google+Share on Google+

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

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

Ads

View Answers

March 16, 2012 at 4:54 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);
    }

     }
 }









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 Retrieve database from the table dynamically in jsp from oracle using servlet What does core Java include? java What are some way to learn Java quickly? Is it required to learn Java before learning Java Script? Is it necessary to learn java script before learning PHP? Are HTML5 and Java Script boosts Java career? Is Java object oriented? Fingerprint application with Java Uninstall Oracle Virtual Box JSON to HashMap Free Java online Training I want example of Control Statement in Java ANSI Color Codes with Python Create a Program that Calculates Input What is difference between JDK,JRE and JVM? How to see ubuntu version on server? How to get Page Source in Selenium (WebDriver) using Java? The path to the driver executable must be set by the webdriver.gecko.driver system property parse data from a link in java Java Program Qns using BlueJ How to fix HAX Kernel Module Is Not Installed error? Installing Audacity Looking for code Logic to check track changes & Coments in MSWord, MSWordx, MSExcel, MSExcelx is ON/OFF Installing JDK on Mac SAX Parser exception ERROR 601 (42P00): Syntax error. Encountered Thread java.lang.NoClassDefFoundError: org/apache/commons/fileupload/FileItemFactory How to install Ubuntu 16.04 LTS? HttpServletRequest cannot be resolved to a type in eclipse - Solved Unhandled event loop exception GC overhead limit exceeded Spring Data jpa with apache phoenix Caused by: java.lang.IllegalArgumentException: Not a host:port pair: PBUF o.a.h.h.z.RecoverableZooKeeper - Possibly transient ZooKeeper, quorum= com.thinkaurelius.titan.diskstorage.hbase.HBaseStoreManager class not found com.thinkaurelius.titan.diskstorage.hbase.HBaseStoreManager not found How to download and install Java 8 on Windows? How to uninstall JDK 7? How to install gtk-doc-tools package in Ubuntu? How to install Oracle JDK 8 on Ubuntu? ejabberd_ctl.beam not found - Solved How to convert date to UTC format in Java? How to install autoconf, automake and libtool in Ubuntu 15.10? How to convert current date to mm dd yyyy format in Java? How to convert current date to dd mm yyyy format in Java? How to stop window closing in "internalFrameClosing" event. How to find list of all index in Neo4j? neo4j-server.properties file location SASLError using PLAIN: not-authorized

Ads

 
Advertisement null

Ads