Algoritmo de Dijkstra - Encontrar la ruta más corta
Lista de aristas: (Haz Shift + clic y arrastra para crear aristas)
Resultados:
Seleccione nodos de inicio y destino, luego haga clic en "Calcular ruta más corta".
Explicación del Algoritmo de Dijkstra
El algoritmo de Dijkstra encuentra la ruta más corta entre dos nodos en un grafo con pesos no negativos:
- Inicialización: Asignar distancia cero al nodo inicial e infinito a todos los demás nodos.
- Selección: Seleccionar el nodo no visitado con la menor distancia temporal.
- Actualización: Para cada vecino del nodo actual, calcular su distancia tentativa y actualizarla si es menor.
- Marcado: Marcar el nodo actual como visitado.
- Repetición: Repetir los pasos 2-4 hasta que todos los nodos estén visitados o se alcance el nodo destino.
Complejidad: O(n²) para la implementación básica, donde n es el número de nodos.