Back خوارزمية بلمان فورد Arabic Алгоритъм на Белман-Форд Bulgarian Algorisme de Bellman-Ford Catalan Bellmanův–Fordův algoritmus Czech Bellman-Ford-Algorithmus German Bellman–Ford algorithm English Algoritmo de Bellman-Ford Spanish الگوریتم بلمن–فورد Persian Algorithme de Bellman-Ford French אלגוריתם בלמן-פורד HE
| Algoritmo di Bellman-Ford | |
|---|---|
| Classe | Cammino minimo |
| Struttura dati | Grafo |
| Caso peggiore temporalmente | |
L'algoritmo di Bellman-Ford calcola i cammini minimi di un'unica sorgente su un grafo diretto pesato (dove alcuni pesi degli archi possono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiede che i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archi negativi[1][2].
Secondo Robert Sedgewick «i pesi negativi non sono solamente una curiosità matematica; […] si presentano in modo naturale quando riduciamo altri problemi a quelli di cammini minimi» e forniscono un esempio specifico di una riduzione dal problema NP-completo del cammino hamiltoniano. Se un grafo contiene un ciclo di peso totale negativo allora sono ottenibili pesi arbitrariamente piccoli e quindi non c'è soluzione; Bellman-Ford individua questo caso[3][4].
- ^ homepages.cwi.nl (PDF).
- ^ O'Reilly - Safari Books Online - 0201361213 - Algorithms in Java, Third Edition, Part 5: Graph Algorithms, su web.archive.org, 31 maggio 2008. URL consultato il 30 ottobre 2021 (archiviato dall'url originale il 31 maggio 2008).
- ^ mitt.uib.no.
- ^ Che cos'è Algoritmo di Bellman-Ford. Enciclopedia, su it.what-this.com. URL consultato il 30 ottobre 2021.