Taller: Algoritmo de Dijkstra ‐ Central City (The Flash) - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki

Fecha de entrega: lunes 28 de julio de 2025
Estudiante: Emilio Jose Peña Armijos

1. Introducción

Este proyecto presenta una implementación del algoritmo de Dijkstra utilizando el patrón Modelo-Vista-Controlador (MVC) en Java. El contexto se basa en Central City, la ciudad ficticia del universo DC donde opera The Flash. Se modela una red de caminos dentro de la ciudad con el objetivo de encontrar la ruta más corta desde un nodo origen (Barry Allen) hacia todos los puntos de interés.

2. Implementación en Java (MVC)

Código completo

import java.util.*;

class Nodo {
    String nombre;
    List<Arista> adyacentes = new ArrayList<>();
    int distancia = Integer.MAX_VALUE;
    Nodo anterior;

    Nodo(String nombre) {
        this.nombre = nombre;
    }
}

class Arista {
    Nodo destino;
    int peso;

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

class Grafo {
    Map<String, Nodo> nodos = new HashMap<>();

    void agregarArista(String origen, String destino, int peso) {
        nodos.putIfAbsent(origen, new Nodo(origen));
        nodos.putIfAbsent(destino, new Nodo(destino));
        nodos.get(origen).adyacentes.add(new Arista(nodos.get(destino), peso));
        nodos.get(destino).adyacentes.add(new Arista(nodos.get(origen), peso)); // No dirigido
    }

    void dijkstra(String inicio) {
        Nodo nodoInicio = nodos.get(inicio);
        nodoInicio.distancia = 0;
        PriorityQueue<Nodo> cola = new PriorityQueue<>(Comparator.comparingInt(n -> n.distancia));
        cola.add(nodoInicio);

        while (!cola.isEmpty()) {
            Nodo actual = cola.poll();
            for (Arista arista : actual.adyacentes) {
                Nodo vecino = arista.destino;
                int nuevaDistancia = actual.distancia + arista.peso;
                if (nuevaDistancia < vecino.distancia) {
                    vecino.distancia = nuevaDistancia;
                    vecino.anterior = actual;
                    cola.add(vecino);
                }
            }
        }
    }

    void mostrarRutas(String inicio) {
        for (Nodo nodo : nodos.values()) {
            System.out.print("Ruta más corta de " + inicio + " a " + nodo.nombre + ": ");
            imprimirCamino(nodo);
            System.out.println(" (Distancia: " + nodo.distancia + ")");
        }
    }

    void imprimirCamino(Nodo nodo) {
        if (nodo.anterior != null) {
            imprimirCamino(nodo.anterior);
            System.out.print(" -> ");
        }
        System.out.print(nodo.nombre);
    }
}

public class CentralCityApp {
    public static void main(String[] args) {
        Grafo grafo = new Grafo();

        grafo.agregarArista("Barry Allen", "Laboratorio STAR", 3);
        grafo.agregarArista("Barry Allen", "Café Jitters", 2);
        grafo.agregarArista("Laboratorio STAR", "Comisaría CCPD", 4);
        grafo.agregarArista("Café Jitters", "Comisaría CCPD", 6);
        grafo.agregarArista("Comisaría CCPD", "Casa de Iris", 1);
        grafo.agregarArista("Café Jitters", "Casa de Iris", 7);

        grafo.dijkstra("Barry Allen");
        grafo.mostrarRutas("Barry Allen");
    }
}

3. Resultados Obtenidos

Salida esperada por consola (prueba de escritorio)

Ruta más corta de Barry Allen a Barry Allen: Barry Allen (Distancia: 0)
Ruta más corta de Barry Allen a Laboratorio STAR: Barry Allen -> Laboratorio STAR (Distancia: 3)
Ruta más corta de Barry Allen a Café Jitters: Barry Allen -> Café Jitters (Distancia: 2)
Ruta más corta de Barry Allen a Comisaría CCPD: Barry Allen -> Laboratorio STAR -> Comisaría CCPD (Distancia: 7)
Ruta más corta de Barry Allen a Casa de Iris: Barry Allen -> Laboratorio STAR -> Comisaría CCPD -> Casa de Iris (Distancia: 8)

4. Análisis

  • ¿Qué garantiza el algoritmo de Dijkstra?
    Encuentra el camino más corto desde el nodo origen a todos los demás, siempre que las aristas tengan pesos no negativos.

  • ¿Cómo se ve afectado el resultado si se agrega un nodo intermedio con menor peso?
    El camino se optimiza automáticamente si una nueva ruta ofrece menor distancia acumulada.

  • ¿Qué utilidad tiene en la vida real?
    Es útil en sistemas de navegación, redes de comunicación, logística y planificación urbana.

5. Conclusiones

El algoritmo de Dijkstra aplicado a un contexto de ciudad permite simular cómo un héroe como The Flash puede optimizar sus rutas de patrullaje. Se evidencia que el patrón MVC ayuda a estructurar el código para mantenerlo escalable y mantenible. Además, la implementación en Java demuestra una gestión efectiva de estructuras de datos como colas de prioridad y mapas hash.

⚠️ **GitHub.com Fallback** ⚠️