SHARE
TWEET

Untitled

a guest Mar 18th, 2019 109 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. class Vertex implements Comparable<Vertex> {
  4.     public final String nombre;
  5.     public Arista[] adj;
  6.     public double minDistancia = Double.POSITIVE_INFINITY;
  7.     public Vertex previo;
  8.  
  9.     public Vertex(String argNombre){
  10.         nombre = argNombre;
  11.     }
  12.  
  13.     public String toString() {
  14.         return nombre; }
  15.  
  16.     public int compareTo(Vertex otro) {
  17.         return Double.compare(minDistancia, otro.minDistancia);
  18.     }
  19. }
  20.  
  21. class Arista {
  22.     public final Vertex objetivo;
  23.  
  24.     public Arista(Vertex argObjetivo) {
  25.         objetivo = argObjetivo;
  26.     }
  27. }
  28.  
  29. class Dijkstra {
  30.     public static void computerutas(Vertex fuente) {
  31.         fuente.minDistancia = 0.;
  32.         PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
  33.         vertexQueue.add(fuente);
  34.  
  35.         while (!vertexQueue.isEmpty()) {
  36.             Vertex u = vertexQueue.poll();
  37.  
  38.             // Visit each Arista exiting u
  39.             for (Arista e : u.adj) {
  40.                 Vertex v = e.objetivo;
  41.                 double distanceThroughU = u.minDistancia;
  42.                 if (distanceThroughU < v.minDistancia) {
  43.                     vertexQueue.remove(v);
  44.  
  45.                     v.minDistancia = distanceThroughU ;
  46.                     v.previo = u;
  47.                     vertexQueue.add(v);
  48.                 }
  49.             }
  50.         }
  51.     }
  52.  
  53.     public static List<Vertex> getShortestPathTo(Vertex objetivo) {
  54.         List<Vertex> ruta = new ArrayList<Vertex>();
  55.         for (Vertex vertex = objetivo; vertex != null; vertex = vertex.previo)
  56.             ruta.add(vertex);
  57.  
  58.         Collections.reverse(ruta);
  59.         return ruta;
  60.     }
  61.  
  62.     public static void main(String[] args) {
  63.  
  64.  
  65.         // primera ruta es horizontal
  66.                     Vertex A = new Vertex("140");
  67.                     Vertex B = new Vertex("134");
  68.                     Vertex C = new Vertex("Lawrence");
  69.                     Vertex D = new Vertex("100");
  70.                     Vertex E = new Vertex("30");
  71.                     Vertex F = new Vertex("R");
  72.                     Vertex G = new Vertex("Summerhill");
  73.                     Vertex H = new Vertex("Warden");
  74.                     Vertex I = new Vertex("Broadview");
  75.  
  76.         //la segunda ruta es vertical a R
  77.                     Vertex J = new Vertex("Eglinton");
  78.                     Vertex K = new Vertex("19");
  79.                     Vertex L = new Vertex("Kennedy");
  80.                     Vertex M = new Vertex("Chester");
  81.  
  82.         //la tercera ruta es vertical a Warden
  83.                     Vertex N = new Vertex("Midland");
  84.                     Vertex O = new Vertex("Yorkdale");
  85.                     Vertex P = new Vertex("Davisville");
  86.                     Vertex Q = new Vertex("Donalds");
  87.  
  88.  
  89.         // Aristas
  90.         A.adj = new Edge[]{ new Edge(B) };
  91.                     B.adj = new Edge[]{ new Edge(C) };
  92.                     C.adj = new Edge[]{ new Edge(D) };
  93.                     D.adj = new Edge[]{ new Edge(E) };
  94.                     E.adj = new Edge[]{ new Edge(F) };
  95.                     F.adj = new Edge[]{ new Edge(G) };  //intersection
  96.                     G.adj = new Edge[]{ new Edge(H) };
  97.                     H.adj = new Edge[]{ new Edge(I) };  //intersection
  98.                     I.adj = new Edge[]{ new Edge(I) };
  99.  
  100.                     J.adj = new Edge[]{ new Edge(J) };
  101.                     K.adj = new Edge[]{ new Edge(F) };
  102.                     L.adj = new Edge[]{ new Edge(F) };
  103.                     M.adj = new Edge[]{ new Edge(M) };
  104.  
  105.                     N.adj = new Edge[]{ new Edge(N) };
  106.                     O.adj = new Edge[]{ new Edge(N) };
  107.                     P.adj = new Edge[]{ new Edge(O) };
  108.                     Q.adj = new Edge[]{ new Edge(Q) };          
  109.  
  110.         //List<Vertex> ruta = null;
  111.         //ruta = getShortestPathTo(whatever station the user chooses);
  112.  
  113.         //System.out.println("Ruta: " + ruta);
  114.     }
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top