8/13/2019 Bellman Ford Dijsktrz

1/7

1

DEPARTAMENTO DE ELCTRICA YELECTRNICA

COMUNICACIN DE DATOS

DEBER N.-8

Nombre: Daniela Flores

Fecha:09/06/2013

SANGOLQU-ECUADOR

8/13/2019 Bellman Ford Dijsktrz

2/7

2

ndice de Contenido1. Tema.................................................................................................................................... 3

2. Consulta............................................................................................................................... 3

2.1 BELLMAN-FORD......................................................................................................... 3

Definicin..................................................................................................................... 3

2.2 DIJKSTRA..................................................................................................................... 3

Definicin..................................................................................................................... 3

3. Ejercicios............................................................................................................................. 4

3.1 BELLMAN-FORD......................................................................................................... 4

3.2 DIJSKTRZ..................................................................................................................... 5

4. Bibliografa......................................................................................................................... 7

8/13/2019 Bellman Ford Dijsktrz

3/7

3

1. TemaALGORITMOS: BELLMAN-FORD Y DIJKSTRA

2. Consulta2.1BELLMAN-FORDDefinicin

Determina la ruta ms corta desde un nodo origen hacia los dems nodos

para ello es requerido como entrada un grafo cuyas aristas posean pesos.

La diferencia de este algoritmo con los dems es que los pesos pueden

tener valores negativos ya que Bellman-Ford permite detectar la

existencia de un ciclo negativo.

Este tipo de algoritmo era original de ruteo del ARPANET. Su modo defuncionamiento es el siguiente:

Cada ruteador mantiene una tabla (un vector) que almacena lasmejores distancias conocidas a cada destino y las lneas a usar

para cada destino. Se actualizan las tablas intercambiando

informacin con los vecinos.

La tabla de un ruteador almacena una entrada para cada uno delos ruteadores en la subred (los ruteadores son los ndices). Las

entradas almacenan la lnea preferida de salida y una estimacin

del tiempo o la distancia al destino. Se pueden usar mtricas

distintas (saltos, retrasos, etc.).

Cada ruteador tiene que medir las distancias a sus vecinos. Porejemplo, si la mtrica es el retraso, el ruteador la puede medir

usando paquetes de eco.

Cada T msegs los ruteadores intercambian sus tablas con susvecinos. Un ruteador usa las tablas de sus vecinos y sus

mediciones de las distancias a sus vecinos para calcular una nueva

tabla.

2.2DIJKSTRADefinicin

Determina el camino ms corto dado un vrtice origen al resto de

vrtices en un grafo con pesos en cada arista.

Buscar todos los caminos ms cortos que parten del vrtice origen y que

llevan a todos los dems vrtices; cuando se obtiene el camino ms corto

8/13/2019 Bellman Ford Dijsktrz

4/7

4

desde el vrtice origen, al resto de vrtices que componen el grafo, el

algoritmo se detiene.

Bsqueda de costo uniforme, pero no funciona en grafos con aristas de

coste negativo.

Es un algoritmo greddy. Trabaja por etapas, y toma en cada etapa la mejor solucin sin

considerar consecuencias futuras.

El ptimo encontrado en una etapa puede modificarseposteriormente si surge una solucin mejor.

3. Ejercicios3.1BELLMAN-FORD

Encontrar el camino mnimo desde todos los nodos al vrtice 1. La distancia

mnima desde el nodo que aparece en el subndice al vrtice destino como el

vrtice 1.

1. Inicializar todas las distancias mnimas a INFINITO.

8/13/2019 Bellman Ford Dijsktrz

5/7

5

2. Actualizar el paso anterior, aplicando las frmulas. La distancia de losnodos que tienen accesos directos al vrtice 1 se suma la distancia

mnima acumulada que hay hasta el vrtice oportuno. La distancia

acumulada sera 0 para 1, debido a que la distancia es el mismo, e infinito

para el resto.

3. La distancia mnima acumulada desde los nodos 2 y 3 hasta se actualizalas distancias mnimas de los nodos 4 y 5.

4. Se van actualizando las distancias mnimas acumuladas (D) de losdistintos vrtices hasta 1, y se van utilizando para optimizar el camino

mnimo.

3.2DIJSKTRZ1.Inicializacin

2.Elegir un vrtice w V - {A} tal que D[w] sea mnimo, y agregar w alconjunto solucin S

3.Cada v {C, D, E} hacer D[v] min( D[v], D[w]+C[w, v] )

8/13/2019 Bellman Ford Dijsktrz

6/7

6

4.Elegir un vrtice w V - {A, B} tal que D[w] sea mnimo, y agregar w alconjunto solucin S.

5.Paso 5: Para cada v {C, E} hacer D[v] min( D[v], D[w]+C[w, v]

6.Elegir un vrtice w V - {A, B, D} tal que D[w] sea mnimo, y agregar w alconjunto solucin S.

7.Para cada v { E} hacer D[v] min( D[v], D[w]+C[w, v]

8/13/2019 Bellman Ford Dijsktrz

7/7

7

8.Elegir un vrtice w V - {A, B, D, C} tal que D[w] sea mnimo, y agregar wal conjunto solucin S.

4. Bibliografa Url:http://jariasf.wordpress.com/2013/01/01/camino-mas-corto-algoritmo-de-

bellman-ford/Extrado:08/06/2013 Hora:21:00 pm.

Url:http://trajano.us.es/~rafa/REDES/apuntes/Bellman-Ford.pdfExtrado:08/06/2013 Hora:21:30 pm.

Url: http://www.slideshare.net/guest4ce8197/bellman-fordjueves-4172933Extrado:08/06/2013 Hora:21:45 pm.

Url: http://www.ecured.cu/index.php/Algoritmo_de_DijkstraExtrado:08/06/2013 Hora:22:00 pm.

Url: http://www.slideshare.net/joemmanuel/algoritmo-de-dijkstraExtrado:08/06/2013 Hora:22:30 pm.

Url: http://www.slideshare.net/luisfleal2010/algoritmo-dijkstra-ejemplo-n-2-6090018

Extrado:08/06/2013 Hora:22:45 pm.

http://www.ecured.cu/index.php/Archivo:Algo11.JPG