algoritmo di Bellman–Ford
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
algoritmo per trovare in un grafo con pesi negativi il percorso più breve da una sorgente singola
Key facts
- Class
- Single-source shortest path problem (for weighted directed graphs)
- Data structure
- Graph
- Worst case performance
- Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
- Best case performance
- Θ ( | E | ) {\displaystyle \Theta (|E|)}
- Worst case space complexity
- Θ ( | V | ) {\displaystyle \Theta (|V|)}
via Wikipedia infobox
Article · Italiano
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. 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.
Abstract from DBpedia / Wikipedia · CC BY-SA