Bellman Ford Dijsktrz

Embed Size (px)

Citation preview

  • 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