algoritmo de Bellman–Ford
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
algorithm for finding single-source shortest paths in graphs, allowing some edge weights to be negative
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 · Español
El algoritmo de Bellman-Ford genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford. Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad matemática; […] surgen de una forma natural en la reducción a problemas de caminos más cortos”, y son un ejemplo de una reducción del problema del camino hamiltoniano que es NP-completo hasta el problema de caminos más cortos con pesos generales. Si un grafo contiene un ciclo de coste total negativo entonces este grafo no tiene solución. El algoritmo es capaz de detectar este caso. Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará el camino más corto que no repite ningún vértice. La complejidad de este problema es al menos la del problema del camino más largo de complejidad NP-Completo.
Abstract from DBpedia / Wikipedia · CC BY-SA