algoritmo de bellman ford y dijkstra

Algoritmo de bellman Ford y dijkstra


INDICE
INDICE ii
INTRODUCCIÓN iii
OBJETIVOS iv
1. ALGORITMO DE BELLMAN - FORD 5
1.1. DESCRIPCION DEL PROBLEMA 5
1.2. EXPLICACIÓN DEL ALGORITMO 6
1.3. ANÁLISIS DEL ALGORITMO 6
2. ALGORITMO DE DIJKSTRA 8
2.1. DESCRIPCION DEL ALGORITMO DE DIJKSTRA 9
2.2. EJEMPLOS DE UN ALGORITMO DE DIJKSTRA 10
CONCLUSIONES 14
WEBIBLIOGRAFÍA 15

1.
2.
3.INTRODUCCIÓN
4.
5.
6.
7.
8.
9. En este trabajo se pretende dar a conocer el algoritmo de Bellman-Ford definiendo cada una de las complejidades y los avances de este, para encontrar las soluciones al problema.
10.
11.
12. OBJETIVOS
13.
14.
15.
Dar a conocer el algoritmo Bellman-Ford y DIJKSTRA
Comprender el uso del algoritmo.
Enriquecer conocimientos para el avance en nuestracarrera.

16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
1. ALGORITMO DE BELLMAN - FORD
29. El algoritmo de Bellman-Ford (algoritmo de Bell-End-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 requiereque los pesos de las aristas no sean negativos. 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.
30.
31. 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áscortos”, 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.
32. Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará elcamino 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.
1.1. DESCRIPCION DEL PROBLEMA
33. 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 relajatodas 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 casogeneral.
34.
35.
36.
37.
1.2. EXPLICACIÓN DEL ALGORITMO
38. En el paso 0, inicializamos todas las distancias o costos mínimos a infinito.
39. En el paso 1, actualizamos el paso anterior, aplicando las fórmulas. En este caso ponemos la distancia de los nodos que tienen accesos directos al vértice 1, y se la sumamos a la distancia mínima acumulada que hay hasta el vértice oportuno.Aquí esta distancia acumulada sería 0 para 1, debido que sería la distancia a él mismo, e infinito para el resto porque no han sido analizados todavía.
40. En el paso 2, al saber ya una distancia mínima acumulada desde los nodos 2 y 3 hasta 1, podemos actualizar las distancias mínimas de los nodos 4 y 5.
41. En los pasos sucesivos, se van actualizando las distanciasmínimas acumuladas de los distintos vértices hasta 1, y se van utilizando en los pasos siguientes para optimizar el camino mínimo. El final del algoritmo se da cuando no hay ningún cambio de un paso a otro, cuando ya no se puede encontrar un camino más corto.
42.
1.3. ANÁLISIS DEL ALGORITMO
43. Mediante un ejemplo analizaremos el algoritmo:
44. Procedimiento para hallar el camino mínimo de...