Shortest Path Problem

Shortest Path Problem (SPP) es el problema de hallar el camino de mínimo peso total entre dos nodos en un grafo ponderado (dirigido o no dirigido), en una de tres variantes principales: single-source single-destination (punto a punto), single-source all-destinations (una fuente a todos los destinos) o all-pairs (cada par). Es el problema grafo-OR fundacional; para aristas no negativas la solución canónica es el algoritmo polinómico definido por Dijkstra (1959) en un artículo de dos páginas en *Numerische Mathematik* (implementación binary heap O((V+E)logV)). Para aristas negativas, Bellman-Ford (Bellman 1958) resuelve en O(VE) y detecta ciclos negativos. Para all-pairs, Floyd-Warshall (Floyd 1962) resuelve por programación dinámica en O(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* es el libro de texto canónico. El algoritmo OR más invocado en la industria moderna — se ejecuta bajo servicios de navegación, cartografía, protocolos de enrutamiento de paquetes (OSPF), secuenciación de reparto, planificación de rutas en autopista; en redes viales nacionales, los enfoques modernos basados en preprocesamiento (contraction hierarchies — Geisberger 2008) entregan tiempos de consulta sub-milisegundo. TSP (#068) y VRP (#002) llaman al shortest path como subrutina pero son problemas distintos: shortest path es polinómico, TSP/VRP NP-difícil.