Glossario · approach
Dijkstra Algorithm
Algoritmo polinomiale di Edsger Dijkstra (1959) per cammini minimi single-source su grafi a pesi non negativi; greedy — estrae il nodo non visitato a minima distanza tentativa da una coda di priorità e rilassa i suoi vicini; O((V+E) log V) con binary heap.
Algoritmo di DijkstraDijkstraAlgoritmo DijkstraDijkstra Shortest Path
Algoritmo di Dijkstra è l'algoritmo polinomiale che Edsger Dijkstra definì nel suo articolo di due pagine del 1959 su *Numerische Mathematik*; risolve il problema del cammino minimo single-source (cammino minimo da un nodo sorgente a tutti gli altri nodi) su un grafo con pesi degli archi non negativi. Approccio greedy: a ogni passo, estrarre da una coda di priorità il nodo non visitato con minima distanza tentativa e rilassare (aggiornare) le distanze dei suoi vicini. Complessità: O((V+E) log V) con binary heap, O(E + V log V) con Fibonacci heap. Nella variante single-source single-destination la ricerca si ferma al raggiungere il bersaglio; per single-source all-destinations si elabora l'intero grafo. Fondazionale; subroutine in innumerevoli sistemi pratici (protocolli di routing OSPF, navigazione, distanza nei social network, commutazione di pacchetto). A* (Hart-Nilsson-Raphael 1968) è la variante guidata da euristica di Dijkstra; contraction hierarchies (Geisberger 2008) è l'estensione moderna basata su pre-processing per reti stradali nazionali. Se il grafo ha archi negativi Dijkstra non è ottimo — serve Bellman-Ford. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* è il riferimento didattico.
Örnek
In un'operazione di servizio sul campo, il cammino di tempo minimo dal cliente 1 al cliente 12 è calcolato in millisecondi sul grafo della rete stradale urbana tramite un Dijkstra basato su binary heap; la centrale di dispaccio identifica il tecnico più vicino a una chiamata di emergenza con una variante Dijkstra single-source all-destinations.