Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 222 vistas

    Ejemplo 1 Ruta Más Corta

    Cargado por

    hugo_castrillon_2
    Este documento presenta un ejemplo de cómo determinar la ruta más corta en una red utilizando el algoritmo de Dijkstra. Describe una red con 6 nodos y 7 enlaces, cada uno con un peso asociado. Luego, explica los 5 pasos del algoritmo de Dijkstra para encontrar la ruta más corta desde el nodo O hasta el nodo F, la cual resultó ser O-A-C-E-F con una distancia total de 16 unidades.

    Copyright:

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

    Ejemplo 1 Ruta Más Corta

    Cargado por

    hugo_castrillon_2
    222 vistas6 páginas
    Este documento presenta un ejemplo de cómo determinar la ruta más corta en una red utilizando el algoritmo de Dijkstra. Describe una red con 6 nodos y 7 enlaces, cada uno con un peso asociado. Luego, explica los 5 pasos del algoritmo de Dijkstra para encontrar la ruta más corta desde el nodo O hasta el nodo F, la cual resultó ser O-A-C-E-F con una distancia total de 16 unidades.

    Descripción original:

    Ejemplo 1 Ruta Más Corta

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta un ejemplo de cómo determinar la ruta más corta en una red utilizando el algoritmo de Dijkstra. Describe una red con 6 nodos y 7 enlaces, cada uno con un peso asociado. Luego, explica los 5 pasos del algoritmo de Dijkstra para encontrar la ruta más corta desde el nodo O hasta el nodo F, la cual resultó ser O-A-C-E-F con una distancia total de 16 unidades.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    222 vistas6 páginas

    Ejemplo 1 Ruta Más Corta

    Cargado por

    hugo_castrillon_2
    Este documento presenta un ejemplo de cómo determinar la ruta más corta en una red utilizando el algoritmo de Dijkstra. Describe una red con 6 nodos y 7 enlaces, cada uno con un peso asociado. Luego, explica los 5 pasos del algoritmo de Dijkstra para encontrar la ruta más corta desde el nodo O hasta el nodo F, la cual resultó ser O-A-C-E-F con una distancia total de 16 unidades.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 6

    EJEMPLO No 1 : DETERMINAR LA RUTA MS CORTA DE LA SIGUIENTE RED

    A D

    4 3 7
    5

    O C F

    2
    4 5
    6

    B E

    El modelo de la ruta ms corta se refiere a una red en la cual cada arco ( i , j ) tiene asociado un nmero, c ij , el cual se
    interpreta como la distancia (o tal vez el costo o el tiempo) desde el nodo i hasta el nodo j . Una ruta o camino entre dos
    nodos es cualquier secuencia de arcos que los conecte. El objetivo consiste en encontrar las rutas ms cortas (o de
    menor costo o ms rpidas) desde un nodo especifico hasta cada uno de los dems nodos de la red.
    A (5, - )(0 ) D

    4 3 7
    5

    (0, - )(0 ) O C F

    2
    4 5
    6

    B E

    (4, - )(0 )

    PRIMER PASO DEL: Algoritmo de Dijkstra

    ETIQUETADO:
    O El color rojo indica

    (4, - ) (0 )
    Iteracin
    que es un nodo
    permanente
    ACUMULADO Nmero de
    PROCEDENCIA Iteraciones
    Distancia desde el inicio hasta
    realizadas
    este Nodo De que nodo
    procede
    A (5, - )(0) D

    4 3 7
    5

    (0, - )(0) O C (10, B )(1 ) F

    2
    4 5
    6

    B E

    (4, - )(0)

    PASO No 2

    Selecciono la distancia acumulada ms corta entre los nodos A y B


    Selecciono el nodo B y lo vuelvo permananente color rojo
    Eteiqueto las conexiones de B, en este caso el nodo C
    A (5, - )(0)
    (1 )
    D

    4 3 7
    5

    (0, - )(0)
    (1 ) O C (9, A )(2(3 ) F

    2
    4 5
    6

    B E

    (4, - )(0)

    PASO No 3

    Comparo las distancias de 10 de BC y 5 de OA y selecciono la ms corta


    Vuelvo permanente al nodo A yactualizo la conexin hacia C
    La distancia acumulada del nodo C procedente de A es de 9
    (12, C )(3)
    A (5, - )(0)
    (1 )
    D

    4 3 7
    5

    (0, - )(0)
    (1 ) O C (9, A )(2(3 ) F

    2
    4 5
    6

    B E (11, C )(3)
    (4, - )(0)

    PASO No 4:
    Volvemos permanente el Nodo C y etiquetamos las conecciones hacia D y E
    (12, C )(3)
    (4)
    A (5, - )(0)
    (1 )
    D

    4 3 7
    5
    (16, E )(4)
    (0, - )(0)
    (1 ) O C (9, A )(2(3 ) F

    2
    4 5
    6

    B E (11, C )(3)
    (4)

    (4, - )(0)

    PASO No 5:
    SOLUCIN:
    Selecciono la distancia ms corta desde C La ruta ms corta desde O hasta F es :
    Elijo al nodo E y lo vuelvo permanente O-A-C-E-F
    Elijo el nodo F y lo vuelvo permanente y calculo distancia La distancia recorrida es de: 16 Unidades

    También podría gustarte