Calculadora de Camino más Corto de Dijkstra

Bienvenido a la Calculadora de camino más corto de Dijkstra, una herramienta interactiva para encontrar los caminos más cortos en grafos ponderados utilizando el algoritmo de Dijkstra. Ya sea que seas un estudiante de ciencias de la computación aprendiendo teoría de grafos, un profesional de redes analizando protocolos de enrutamiento o un desarrollador implementando búsqueda de caminos, esta calculadora ofrece una exploración visual paso a paso de uno de los algoritmos más fundamentales de la informática.

¿Qué es el algoritmo de Dijkstra?

El algoritmo de Dijkstra, inventado por el científico informático holandés Edsger W. Dijkstra en 1956, es un algoritmo de búsqueda en grafos que resuelve el problema del camino más corto desde un único origen para un grafo ponderado con pesos de arista no negativos. Dado un nodo origen, encuentra el camino más corto desde ese nodo a cualquier otro nodo del grafo.

El algoritmo funciona manteniendo un conjunto de nodos no visitados y seleccionando repetidamente el nodo no visitado con la distancia tentativa más pequeña (una estrategia codiciosa). Esto es lo que lo hace elegante y eficiente: una vez que un nodo es "visitado", su distancia más corta está garantizada como final.

Pseudocódigo del algoritmo

Fórmula central

Donde:

• d[u] = distancia más corta conocida actualmente desde el origen al nodo u
• w(u, v) = peso de la arista de u a v
• d[v] = distancia más corta conocida actualmente desde el origen al nodo v

Cómo usar esta calculadora

1. Defina las aristas de su grafo: Ingrese las aristas en el formato origen, destino, peso, una por línea. Cada línea representa una conexión entre dos nodos.
2. Elija el tipo de grafo: Seleccione "No dirigido" para aristas de doble sentido (como carreteras) o "Dirigido" para aristas de un solo sentido (como rutas aéreas o enlaces web).
3. Establezca el nodo origen: Ingrese el nodo de inicio desde el cual se calcularán todos los caminos más cortos.
4. Encuentre los caminos más cortos: Haga clic en el botón para ejecutar el algoritmo de Dijkstra. Explore la visualización interactiva del grafo, la tabla de distancias y la traza paso a paso.
5. Recorra los pasos: Use los botones Siguiente/Anterior para ver la ejecución del algoritmo paso a paso, con el grafo resaltando los nodos y aristas actualizados en tiempo real.

Entendiendo los resultados

Tabla de distancias

Muestra la distancia más corta desde el origen a cada nodo, junto con el camino completo. Los nodos marcados con ∞ son inalcanzables desde el origen.

Visualización del grafo

El lienzo interactivo muestra su grafo con nodos y aristas codificados por colores:

• Nodo azul = Nodo origen
• Nodos verdes = Visitados (distancia finalizada)
• Nodo naranja = Actualmente en proceso
• Nodos grises = Aún no visitados
• Aristas verdes = Árbol de caminos más cortos

Traza paso a paso

Muestra la ejecución del algoritmo, incluyendo extracciones de la cola de prioridad, relajaciones de aristas y actualizaciones de distancia en cada paso. Esto es invaluable para aprender cómo funciona el algoritmo.

Complejidad temporal

La eficiencia del algoritmo de Dijkstra depende de la estructura de datos utilizada para la cola de prioridad:

Donde V es el número de vértices (nodos) y E es el número de aristas. Esta calculadora utiliza una implementación de montículo binario.

Grafos dirigidos frente a no dirigidos

• Grafo no dirigido: Una arista entre A y B significa que puedes viajar tanto A→B como B→A. Ejemplos: redes de carreteras, redes de amistad, circuitos eléctricos.
• Grafo dirigido: Una arista de A a B solo permite viajar A→B, no necesariamente B→A. Ejemplos: hipervínculos web, seguidores de Twitter, rutas aéreas, flujo de un río.

Limitaciones del algoritmo de Dijkstra

• Sin pesos negativos: El algoritmo de Dijkstra produce resultados incorrectos con pesos de arista negativos. Use Bellman-Ford para grafos con pesos negativos (pero sin ciclos negativos).
• Origen único: Encuentra los caminos más cortos desde un solo origen. Para caminos más cortos entre todos los pares, use Floyd-Warshall o ejecute Dijkstra desde cada nodo.
• Sin ciclos negativos: Los ciclos negativos hacen que los caminos más cortos no estén definidos (siempre puedes recorrer el ciclo para reducir la distancia infinitamente).

Aplicaciones en el mundo real

Navegación GPS

Los servicios de mapas utilizan variantes del algoritmo de Dijkstra (a menudo con heurísticas A*) para encontrar la ruta más rápida entre dos ubicaciones. Las intersecciones de carreteras son nodos y los segmentos de carretera son aristas ponderadas (por tiempo o distancia).

Enrutamiento de red

Los protocolos de enrutamiento de Internet como OSPF (Open Shortest Path First) e IS-IS utilizan el algoritmo de Dijkstra para calcular los caminos más cortos a través de las topologías de red. Cada enrutador construye un árbol de caminos más cortos para determinar el reenvío de paquetes.

Análisis de redes sociales

Encontrar el camino de conexión más corto entre usuarios (grados de separación), calcular medidas de centralidad e identificar nodos influyentes en una red.

Desarrollo de videojuegos

La búsqueda de caminos para los personajes no jugables (NPC) en los videojuegos utiliza el algoritmo de Dijkstra o A* (que extiende a Dijkstra con heurísticas) para navegar por los mapas del juego y encontrar rutas de movimiento óptimas.

Cadena de suministro y logística

Optimización de rutas de entrega, trayectos de almacén a tienda y redes de transporte multimodal donde diferentes métodos de transporte tienen diferentes costes.

Preguntas frecuentes

¿Qué es el algoritmo de Dijkstra?

El algoritmo de Dijkstra es un algoritmo de búsqueda en grafos que encuentra el camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado con pesos de arista no negativos. Utiliza una estrategia codiciosa con una cola de prioridad (min-heap), procesando siempre el nodo no visitado con la distancia conocida más pequeña. La complejidad temporal es O((V + E) log V) con un montículo binario.

¿Puede el algoritmo de Dijkstra manejar pesos de arista negativos?

No, el algoritmo de Dijkstra requiere que todos los pesos de las aristas sean no negativos. Los pesos negativos pueden causar que el algoritmo produzca resultados incorrectos porque una vez que un nodo se marca como visitado, su distancia se considera final. Para grafos con pesos negativos (pero sin ciclos negativos), use el algoritmo de Bellman-Ford en su lugar.

¿Cuál es la diferencia entre grafos dirigidos y no dirigidos?

En un grafo dirigido, las aristas tienen una dirección: una arista de A a B no implica una arista de B a A. En un grafo no dirigido, las aristas funcionan en ambos sentidos: si hay una conexión entre A y B, puedes viajar en cualquier dirección. Las redes de carreteras se modelan típicamente como grafos no dirigidos, mientras que los enlaces web y las rutas aéreas son dirigidos.

¿Qué es la relajación de aristas en el algoritmo de Dijkstra?

La relajación de aristas es la operación central en el algoritmo de Dijkstra. Al visitar un nodo u, para cada vecino v, el algoritmo comprueba si el camino a través de u (dist[u] + peso(u,v)) es más corto que la distancia conocida actual a v (dist[v]). Si es más corto, la distancia se actualiza (se relaja) y v se añade a la cola de prioridad con la nueva distancia.

¿Qué es un árbol de caminos más cortos?

Un árbol de caminos más cortos (SPT) es un subgrafo con raíz en el nodo origen que contiene los caminos más cortos desde el origen a todos los nodos alcanzables. Cada nodo (excepto el origen) tiene exactamente un padre: el predecesor en su camino más corto. El SPT es un subproducto del algoritmo de Dijkstra y es útil para el enrutamiento y el diseño de redes.

¿Cuáles son las aplicaciones del algoritmo de Dijkstra en el mundo real?

El algoritmo de Dijkstra se utiliza en sistemas de navegación GPS, protocolos de enrutamiento de red (OSPF, IS-IS), análisis de redes sociales, optimización de rutas aéreas, planificación de rutas de robots, IA de búsqueda de caminos en juegos, logística de la cadena de suministro y diseño de redes de telecomunicaciones. Cualquier problema que pueda modelarse como la búsqueda del camino más corto o de menor coste en un grafo se beneficia de este algoritmo.