Aplicación para determinar el camino mínimo a partir de un grafo dirigido - psyepez2005/Analisis_De_Algoritmos GitHub Wiki

package caminominimo;
import java.util.*;

class Arista {
    int destino;
    int peso;

    public Arista(int destino, int peso) {
        this.destino = destino;
        this.peso = peso;
    }
}

public class DijkstraGrafoDirigido {
    public static void main(String[] args) {
        int numNodos = 5;
        int origen = 0;

        // Representación del grafo como lista de adyacencia
        List<List<Arista>> grafo = new ArrayList<>();
        for (int i = 0; i < numNodos; i++) {
            grafo.add(new ArrayList<>());
        }

        // Agregar aristas (grafo dirigido)
        grafo.get(0).add(new Arista(1, 10));
        grafo.get(0).add(new Arista(3, 5));
        grafo.get(1).add(new Arista(2, 1));
        grafo.get(1).add(new Arista(3, 2));
        grafo.get(2).add(new Arista(4, 4));
        grafo.get(3).add(new Arista(1, 3));
        grafo.get(3).add(new Arista(2, 9));
        grafo.get(3).add(new Arista(4, 2));
        grafo.get(4).add(new Arista(0, 7));
        grafo.get(4).add(new Arista(2, 6));

        // Ejecutar Dijkstra y mostrar prueba de escritorio
        dijkstraPasoAPaso(grafo, origen);
    }

    public static void dijkstraPasoAPaso(List<List<Arista>> grafo, int origen) {
        int n = grafo.size();
        int[] distancia = new int[n];
        boolean[] visitado = new boolean[n];
        int[] anterior = new int[n];

        Arrays.fill(distancia, Integer.MAX_VALUE);
        Arrays.fill(anterior, -1);
        distancia[origen] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{origen, 0});

        System.out.println("Paso a paso del algoritmo de Dijkstra:");

        while (!pq.isEmpty()) {
            int[] actual = pq.poll();
            int nodo = actual[0];

            if (visitado[nodo]) continue;
            visitado[nodo] = true;

            System.out.println("\nVisitando nodo: " + nodo);
            System.out.println("Distancias antes de actualizar vecinos: " + Arrays.toString(distancia));
            System.out.println("Vecinos del nodo " + nodo + ":");

            for (Arista arista : grafo.get(nodo)) {
                int vecino = arista.destino;
                int peso = arista.peso;
                int distAntes = distancia[vecino];

                System.out.print("  Arista " + nodo + " -> " + vecino + " con peso " + peso);

                if (!visitado[vecino] && distancia[nodo] + peso < distancia[vecino]) {
                    distancia[vecino] = distancia[nodo] + peso;
                    anterior[vecino] = nodo;
                    pq.add(new int[]{vecino, distancia[vecino]});
                    System.out.println("  --> Actualizado: distancia " + distAntes + " -> " + distancia[vecino]);
                } else {
                    System.out.println("  --> No se actualiza (distancia actual: " + distAntes + ")");
                }
            }

            // Mostrar contenido actual de la cola de prioridad
            System.out.print("Cola de prioridad actual: [");
            String colaStr = pq.stream()
                    .map(arr -> "(" + arr[0] + ", dist=" + arr[1] + ")")
                    .reduce((a, b) -> a + ", " + b).orElse("");
            System.out.println(colaStr + "]");
        }

        System.out.println("\n--- Resultado Final ---");
        for (int i = 0; i < n; i++) {
            System.out.print("Distancia mínima a nodo " + i + " = ");
            if (distancia[i] == Integer.MAX_VALUE) {
                System.out.print("∞ (inaccesible)");
            } else {
                System.out.print(distancia[i]);
            }
            System.out.print(" | Camino: ");
            if (distancia[i] == Integer.MAX_VALUE) {
                System.out.println("N/A");
            } else {
                imprimirCamino(i, anterior);
                System.out.println();
            }
        }
    }


    public static void imprimirCamino(int destino, int[] anterior) {
        if (anterior[destino] == -1) {
            System.out.print(destino);
            return;
        }
        imprimirCamino(anterior[destino], anterior);
        System.out.print(" -> " + destino);
    }
}