Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 110 vistas

    Ejer Mop

    Cargado por

    Leonel Enrique Ramos
    Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre una ciudad origen (nodo 1) y cuatro ciudades destino (nodos 2-5) en una red de rutas. Explica cómo el algoritmo itera etiquetando nodos de forma permanente con sus distancias mínimas desde el nodo origen, hasta que todas las rutas más cortas se determinan.

    Copyright:

    © All Rights Reserved
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd

    Ejer Mop

    Cargado por

    Leonel Enrique Ramos
    110 vistas2 páginas
    Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre una ciudad origen (nodo 1) y cuatro ciudades destino (nodos 2-5) en una red de rutas. Explica cómo el algoritmo itera etiquetando nodos de forma permanente con sus distancias mínimas desde el nodo origen, hasta que todas las rutas más cortas se determinan.

    Descripción original:

    ejercicio de iop

    Título original

    ejer mop

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOC, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre una ciudad origen (nodo 1) y cuatro ciudades destino (nodos 2-5) en una red de rutas. Explica cómo el algoritmo itera etiquetando nodos de forma permanente con sus distancias mínimas desde el nodo origen, hasta que todas las rutas más cortas se determinan.

    Copyright:

    © All Rights Reserved
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    110 vistas2 páginas

    Ejer Mop

    Cargado por

    Leonel Enrique Ramos
    Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre una ciudad origen (nodo 1) y cuatro ciudades destino (nodos 2-5) en una red de rutas. Explica cómo el algoritmo itera etiquetando nodos de forma permanente con sus distancias mínimas desde el nodo origen, hasta que todas las rutas más cortas se determinan.

    Copyright:

    © All Rights Reserved
    Descargue como DOC, PDF, TXT o lea en línea desde Scribd
    Descargar como doc, pdf o txt
    de 2

    La red de la figura 6.

    15 da las rutas permisibles y sus longitudes en millas entre la ciudad 1 (nodo


    1) y las otras cuatro ciudades (nodos 2 a 5). Determine las rutas más cortas entre la ciudad 1 y
    cada una de las cuatro ciudades restantes.
    Iteración 0. Asigne una etiqueta permanente [0, -] al nodo 1.
    Iteración 1. Se puede llegar a los nodos 2 y 3 desde el nodo 1 (el último etiquetado
    perma- nentemente). Así, la lista de nodos etiquetados (temporales y
    permanentes) es

    Nodo Etiqueta Estado

    1 [0, —] Permanente
    2 [0 + 100, 1] = [100, 1] Temporal
    3 [0 + 30, 1] = [30, 1] Temporal

    Para las dos etiquetas temporales [100,1] y [30,1], el nodo 3 da la distancia


    míni- ma (u3 = 30). De este modo, el estado del nodo 3 cambia a permanente.
    Iteración 2. Se puede llegar a los nodos 4 y 5 desde el nodo 3, y la lista de los nodos etique-
    tados es

    Nodo Etiqueta Estado

    1 [0, —] Permanente
    2 [100, 1] Temporal
    3 [30, 1] Permanente
    4 [30 + 10, 3] = [40, 3] Temporal
    5 [30 + 60, 3] = [90, 3] Temporal

    La etiqueta temporal [40,3] en el nodo 4 ahora es permanente (u4 = 40).

    2
    15

    4
    100 20
    10 50

    30 60
    1 3 5

    FIGURA 6.15
    Ejemplo de red para el algoritmo de la ruta más corta de Dijkstra
    Iteración 3. Desde el nodo 4 se puede llegar a los nodos 2 y 5 Así, la lista de los nodos
    eti- quetados se actualiza como

    Nodo Etiqueta Estado

    1 [0, —] Permanente
    2 [40 + 15, 4] = [55, 4] Temporal
    3 [30, 1] Permanente
    4 [40, 3] Permanente
    5 [90, 3] o
    [40 + 50, 4] = [90, 4] Temporal

    En el nodo 2, la nueva etiqueta [55,4] reemplaza a la etiqueta temporal


    [100,1] de la iteración 1 porque proporciona una ruta más corta. Además, en
    la itera- ción 3 el nodo 5 tiene dos etiquetas alternativas con la misma
    distancia (u5 = 90). La etiqueta temporal [55,4] en el nodo 2 ahora es
    permanente (u2 = 55).
    Iteración 4. Sólo el nodo 3 permanentemente etiquetado puede ser alcanzado desde el nodo
    2. Por consiguiente el nodo 3 no puede ser reetiquetado. La nueva lista de eti-
    quetas permanece como estaba en la iteración 3 excepto que la etiqueta en el
    nodo 2 ahora es permanente. Esto deja al nodo 5 como la única etiqueta
    tempo- ral. Como el nodo 5 no conduce a otros nodos, su etiqueta se hace
    permanente, y el proceso termina.

    Los cálculos del algoritmo pueden realizarse directamente en la red, como lo demuestra
    la figura 6.16.
    La ruta más corta entre el nodo 1 y cualquier otro nodo en la red se determina partiendo
    del nodo destino deseado y retrocediendo hasta el nodo de inicio utilizando la información en
    las etiquetas permanentes. Por ejemplo, la siguiente secuencia determina la ruta más corta del
    nodo 1 al nodo 2:
    (2) → [55, 4] → (4) → [40, 3] → (3) → [30, 1] → (1)
    Por lo tanto, la ruta deseada es 1 → 3 → 4 → 2 con una distancia total de 55 millas.
    FIGURA 6.16
    Procedimiento de etiquetado en el algoritmo de Dijkstra

    [100,1](1)
    [55,4](3)
    2
    15
    [40,3](2)
    4
    100 20
    10 50

    30 60 [90,3](2)
    [0,—](1) 1 3 5 [90,4](3)

    [30,1](1)

    ( ) = iteración

    También podría gustarte