Shortest Path Problem

Shortest Path Problem (SPP) è il problema di trovare il cammino di peso totale minimo tra due nodi su un grafo pesato (orientato o non orientato), in una di tre varianti principali: single-source single-destination (punto-punto), single-source all-destinations (una sorgente a tutti i destini) o all-pairs (ogni coppia). È il problema grafo-OR fondazionale; per archi non negativi la soluzione canonica è l'algoritmo polinomiale definito da Dijkstra (1959) in un articolo di due pagine su *Numerische Mathematik* (implementazione binary heap O((V+E)logV)). Per archi negativi, Bellman-Ford (Bellman 1958) risolve in O(VE) e rileva cicli negativi. Per all-pairs, Floyd-Warshall (Floyd 1962) risolve per programmazione dinamica in O(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* è il manuale canonico. L'algoritmo OR più invocato nell'industria moderna — gira sotto servizi di navigazione, cartografia, protocolli di routing di pacchetti (OSPF), sequenziamento di consegna pacchi, pianificazione di rotte autostradali; su reti stradali nazionali, gli approcci moderni basati su pre-processing (contraction hierarchies — Geisberger 2008) consegnano tempi di query sub-millisecondo. TSP (#068) e VRP (#002) chiamano shortest path come subroutine ma sono problemi distinti: shortest path è polinomiale, TSP/VRP NP-difficile.