Glosario · approach
Dijkstra Algorithm
Algoritmo polinómico de Edsger Dijkstra (1959) para caminos más cortos single-source en grafos con pesos no negativos; goloso — extrae el nodo no visitado con menor distancia tentativa de una cola de prioridad y relaja sus vecinos; O((V+E) log V) con binary heap.
Algoritmo de DijkstraDijkstraAlgoritmo DijkstraDijkstra Shortest Path
Algoritmo de Dijkstra es el algoritmo polinómico que Edsger Dijkstra definió en su artículo de dos páginas de 1959 en *Numerische Mathematik*; resuelve el problema del camino más corto single-source (camino más corto desde un nodo origen a todos los demás nodos) en un grafo con pesos de aristas no negativos. Enfoque goloso: en cada paso, extraer de una cola de prioridad el nodo no visitado con menor distancia tentativa y relajar (actualizar) las distancias de sus vecinos. Complejidad: O((V+E) log V) con binary heap, O(E + V log V) con Fibonacci heap. En la variante single-source single-destination la búsqueda se detiene al alcanzar el destino; para single-source all-destinations se procesa todo el grafo. Fundacional; subrutina en innumerables sistemas prácticos (protocolos de enrutamiento OSPF, navegación, distancia en redes sociales, conmutación de paquetes). A* (Hart-Nilsson-Raphael 1968) es la variante guiada por heurística de Dijkstra; contraction hierarchies (Geisberger 2008) es la extensión moderna basada en preprocesamiento para redes viales nacionales. Si el grafo tiene aristas negativas, Dijkstra no es óptimo — se necesita Bellman-Ford. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* es la referencia docente.
Örnek
En una operación de servicio en campo, el camino de menor tiempo del cliente 1 al cliente 12 se calcula en milisegundos sobre el grafo de la red vial urbana mediante un Dijkstra basado en binary heap; la central de despacho identifica al técnico más cercano a una llamada de emergencia entrante con una variante Dijkstra single-source all-destinations.