MickyOr

Dijkstra y encontrar ciclos en grafos dirigidos

Apr 29th, 2021
817
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Dijkstra {
  4.   // Encontrar ciclos en grafos dirigidos
  5.   // vis inicia lleno de 0s
  6.   private void dfs(int u, ArrayList<Integer>[] g, int[] vis) {
  7.     // Entrando
  8.     vis[u] = 1;
  9.     for (int v : g[u]) {
  10.       if (vis[v] == 0)  {
  11.         dfs(v, g, vis);
  12.       }
  13.       if (vis[v] == 1) {
  14.         // Hay ciclo
  15.       }
  16.     }
  17.     // Saliendo
  18.     vis[u] = 2;
  19.   }
  20.  
  21.   public static void main(String[] args) {
  22.     Dijkstra sol = new Dijkstra();
  23.     sol.solve();
  24.   }
  25.  
  26.   class Arista {
  27.     private int origen, destino, peso;
  28.    
  29.     public Arista(int origen, int destino, int peso) {
  30.       this.origen = origen;
  31.       this.destino = destino;
  32.       this.peso = peso;
  33.     }
  34.  
  35.     public int getOrigen()  {return origen;}
  36.     public int getDestino() {return destino;}
  37.     public int getPeso()    {return peso;}
  38.   }
  39.  
  40.   public void solve() {
  41.     Scanner sc = new Scanner(System.in);
  42.     int n, m;
  43.     n = sc.nextInt();
  44.     m = sc.nextInt();
  45.     ArrayList<Arista>[] g = new ArrayList[n];
  46.     for (int i = 0; i < n; i++) {
  47.       g[i] = new ArrayList<>();
  48.     }
  49.     for (int i = 0; i < m; i++) {
  50.       int a, b, w;
  51.       a = sc.nextInt();
  52.       b = sc.nextInt();
  53.       w = sc.nextInt();
  54.       g[a].add(new Arista(a, b, w));
  55.       g[b].add(new Arista(b, a, w));
  56.     }
  57.     // DESDE AQUI ES DIJKSTRA
  58.     int[] dist = new int[n];
  59.     int[] par = new int[n];
  60.     ArrayList<Integer> nodosAlcanzados = new ArrayList<>();
  61.     // Inicializacion
  62.     int inicio = 0;
  63.     int inf = 123456789;
  64.     for (int i = 0; i < n; i++) {
  65.       dist[i] = inf;
  66.     }
  67.     dist[inicio] = 0;
  68.     par[inicio] = -1;
  69.     nodosAlcanzados.add(inicio);
  70.     // Encontrar caminos minimos
  71.     while (nodosAlcanzados.size() > 0) {
  72.       int u = nodoMenorDistancia(nodosAlcanzados, dist);
  73.       nodosAlcanzados.remove(Integer.valueOf(u)); // eliminar u de la lista
  74.       System.out.println("Distancia de " + inicio + " a " + u + " = " + dist[u]);
  75.       for (Arista a : g[u]) {
  76.         int v = a.getDestino();
  77.         int w = a.getPeso();
  78.         if (dist[u] + w < dist[v]) {
  79.           dist[v] = dist[u] + w;
  80.           par[v] = u;
  81.           if (nodosAlcanzados.contains(v)) nodosAlcanzados.remove(Integer.valueOf(v));
  82.           nodosAlcanzados.add(v);
  83.         }
  84.       }
  85.     }
  86.     System.out.println("Caminos!");
  87.     for (int i = 0; i < n; i++) {
  88.       System.out.println("Camino hasta " + i);
  89.       ArrayList<Integer> camino = new ArrayList<>();
  90.       int u = i;
  91.       while (u != -1) {
  92.         camino.add(u);
  93.         u = par[u];
  94.       }
  95.       for (int j = camino.size()-1; j >= 0; j--) {
  96.         System.out.print(camino.get(j) + " ");
  97.       }
  98.       System.out.println();
  99.     }
  100.   }
  101.  
  102.   private int nodoMenorDistancia(ArrayList<Integer> nodos, int[] dist) {
  103.     int minDist = 123456789;
  104.     int minNodo = -1;
  105.     for (int u : nodos) {
  106.       if (dist[u] < minDist) {
  107.         minDist = dist[u];
  108.         minNodo = u;
  109.       }
  110.     }
  111.     return minNodo;
  112.   }
  113. }
  114.  
RAW Paste Data