Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Algoritmo de Bellman-Ford
110
CONCLUSIONES
EJEMPLO 2
Concluimos que el algoritmo de Bellman-Ford genera el camino más corto en un grafo dirigido.
El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas NO sean negativos.
EJEMPLO 1
ETIQUETA PARA NODOS DE UN GRAFO
Costo o Peso de la Arista
Nodo Procedente
(A,1)
PSEUDOCÓDIGO
DEFINICIÓN
Este Algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Las repeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez. A diferencia de la solución voraz, la cual depende de la suposición de que los pesos sean positivos, esta solución se aproxima más al caso general.
GRACIAS POR SU ATENCIÓN
INTRODUCCIÓN
En la siguiente presentación explicaremos el algoritmo de Bellman-Ford, que genera el camino más corto en un grafo en el que el peso de alguno de los nodos puede ser negativo.
Se conoce que el algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos.
Por lo que el algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo.
Algoritmo de Bellman-Ford
CONTENIDOS
- Introducción
- Definición
- Pseudocódigo
- Ejemplos
- Conclusión
Por: Luis Muñoz & Juan Arpi