Algorisme de Bellman-Ford

L'algorisme de Bellman-Ford (o algorisme de Bell-End-Ford) genera el camí més curt en un graf dirigit ponderat en què el pes de les arestes pot ser negatiu. L'algorisme de Dijkstra resol aquest mateix problema en un temps menor, però requereix que els pesos de les arestes no siguin negatius. Aquest algorisme va ser desenvolupat per Richard Bellman, Samuel End i Lester Ford.

Segons Robert Sedgewick, "Els pesos negatius no són simplement una curiositat matemàtica; [...] sorgeixen d'una manera natural en la reducció a problemes de camins més curts", i són un exemple d'una reducció del problema del camí hamiltonià que és NP-complet fins al problema de camins més curts amb pesos generals. Si un graf conté un cicle de cost total negatiu llavors aquest graf no té solució. L'algorisme és capaç de detectar aquest cas.

Si el graf conté un cicle de cost negatiu, l'algorisme ho detectés, però no trobarà el camí més curt que no repeteix cap vèrtex. La complexitat d'aquest problema és almenys la del problema del camí més llarg de complexitat NP-Complet.