Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 395 vistas

    Algoritmo de Floyd

    Cargado por

    Ronald Villarreal Gonzales
    El algoritmo de Floyd-Warshall encuentra los caminos más cortos entre todos los pares de nodos en un grafo. Funciona mediante programación dinámica al actualizar iterativamente una matriz de distancias y otra de nodos intermedios hasta obtener las soluciones óptimas. Comienza con las distancias y nodos conocidos y, en cada iteración, revisa si existen caminos más cortos a través de un nodo intermedio.

    Copyright:

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

    Algoritmo de Floyd

    Cargado por

    Ronald Villarreal Gonzales
    395 vistas5 páginas
    El algoritmo de Floyd-Warshall encuentra los caminos más cortos entre todos los pares de nodos en un grafo. Funciona mediante programación dinámica al actualizar iterativamente una matriz de distancias y otra de nodos intermedios hasta obtener las soluciones óptimas. Comienza con las distancias y nodos conocidos y, en cada iteración, revisa si existen caminos más cortos a través de un nodo intermedio.

    Descripción original:

    Algoritmo de Floyd

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El algoritmo de Floyd-Warshall encuentra los caminos más cortos entre todos los pares de nodos en un grafo. Funciona mediante programación dinámica al actualizar iterativamente una matriz de distancias y otra de nodos intermedios hasta obtener las soluciones óptimas. Comienza con las distancias y nodos conocidos y, en cada iteración, revisa si existen caminos más cortos a través de un nodo intermedio.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    395 vistas5 páginas

    Algoritmo de Floyd

    Cargado por

    Ronald Villarreal Gonzales
    El algoritmo de Floyd-Warshall encuentra los caminos más cortos entre todos los pares de nodos en un grafo. Funciona mediante programación dinámica al actualizar iterativamente una matriz de distancias y otra de nodos intermedios hasta obtener las soluciones óptimas. Comienza con las distancias y nodos conocidos y, en cada iteración, revisa si existen caminos más cortos a través de un nodo intermedio.

    Copyright:

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

    ALGORITMO DE FLOYD-WARSHALL

    El algoritmo de Floyd-Warshall es uno de los que se han creado para


    encontrar el camino ms cortos entre nodos, la gracia de este radica en
    que trabaja con programacin dinmica, lo que garantiza que la solucin
    entregada por ste algoritmo es ptima, adems que entrega todos los
    caminos ms cortos para ir desde un nodo i a un nodo j cualquiera y el
    recorrido necesario para completar el dicho recorrido.

    Entrada: Grafo dirigido/no dirigido, con peso asociado a las aristas.


    Salida:
    Matriz Dn que entrega el menor camino para ir de un nodo i a un
    nodo j del grafo.
    Matriz Sn que entrega el nodo intermedio para llegar desde un
    nodo i a un nodo j del grafo.

    Veamos un ejemplo de cmo trabaja el algoritmo:

    Sea el grafo:
    1
    1 8

    2
    4 2

    4 1
    9
    3

    Matriz de Peso Matriz Nodos Intermedios

    D0 1 2 3 4 S0 1 2 3 4
    1 8 1 1 2 3 4
    2 1 2 1 3 4
    3 4 3 1 2 4
    4 2 9 4 1 2 3

    Como vemos ac, el algoritmo no permite que existan nodos que apunten a s
    mismos, ya que las diagonales quedan inhabilitadas.
    La matriz D0 se llena con los pesos de cada camino que representa la
    matriz[i][j] del ejemplo, como vemos, si no existe conexin entre los nodos,
    se completa con el smbolo lo que reprenda que no existe la conexin
    entre los nodos, por lo tanto el peso que trae pasar por ah no se puede
    tasar.

    La matriz S0 se llena con los nodos intermedios entre un par de nodos, en


    este caso suponemos que no existe otro camino entre los nodos que ir
    directamente hacia ellos.

    Luego de completar las primeras matrices, comenzamos fijando una fila


    y una columna pivote, para ver todos los caminos que existen entre el
    nodok y todos los dems, cualquier cambio que ocurra en la matriz de peso,
    incurrir en un cambio en la matriz de nodos intermedios, asumiendo que
    localmente el nodok es el de menor peso en esa iteracin.

    D0 1 2 3 4 S0 1 2 3 4
    1 8 1 1 2 3 4
    2 1 2 1 3 4
    3 4 3 1 2 4
    4 2 9 4 1 2 3

    Fijamos la fila 1, entonces k=1, y comenzamos a revisar el algoritmo


    preguntando si MatrizdePeso[i][k]+MatrizdePeso[k][j]<
    MatrizdePeso[i][j], si es menor se cambia si no se mantiene. As obtenemos
    D1 y S1.

    D1 1 2 3 4 S1 1 2 3 4
    1 8 1 1 2 3 4
    2 1 2 1 3 4
    3 4 12 5 3 1 1 1
    4 2 9 4 1 2 3
    Como se puede ver en las posiciones 3,2 y 3,5 de la matriz de peso, hubo cambios y como
    habamos fijado k =1, entonces en las mismas posiciones se generarn cambios en la matriz
    de nodos intermedios. Ahora fijamos k =2 y seguimos con el procedimiento hasta llegar a k
    =4, que es el nmero total de nodos en el grafo.

    S1 1 2 3 4
    D1 1 2 3 4
    1 2 3 4
    1 8 1
    2 1 3 4
    2 1
    1 1
    3 1
    3 4 12 5
    4 1 2 3
    4 2 9

    D2 1 2 3 4 S2 1 2 3 4
    8 9 1 1 2 2 4
    1
    2 1 2 1 3 4
    3 1 1 1
    3 4 12 5
    4 2 3 4 1 2 2

    Como vemos en las posiciones 1,3 y 4,3 de la matriz de peso, hubo cambios y como
    habamos fijado k =2, entonces en las mismas posiciones se generarn cambios en la matriz
    de nodos intermedios. Ahora fijamos k =3 y seguimos con el procedimiento hasta llegar a k
    =4, que es el nmero total de nodos en el grafo.

    D2 1 2 3 4 S2 1 2 3 4
    1 8 9 1 1 2 2 4
    2 1 2 1 3 4
    3 4 12 5 3 1 1 1
    4 2 3 4 1 2 2
    D3 1 2 3 4 S3 1 2 3 4
    8 9 1 1 2 2 4
    1
    2 5 1 6 2 3 3 3

    12 5 3 1 1 1
    3 4
    4 7 2 3 4 3 2 2

    Como vemos en las posiciones 2,1 ; 2,4 y 4,1 de la matriz de peso, hubo cambios y como
    habamos fijado k =3, entonces en las mismas posiciones se generarn cambios en la matriz
    de nodos intermedios. Ahora fijamos k =4 y seguimos con el procedimiento hasta llegar a k
    =4, que es el nmero total de nodos en el grafo.

    S3 1 2 3 4
    D3 1 2 3 4 2 2 4
    1
    1 8 9 1
    2 3 3 3
    2 5 1 6
    3 1 1 1
    3 4 12 5 4 3 2 2
    4 7 2 3

    S4 1 2 3 4
    D4 1 2 3 4
    1 4 4 4
    1 3 4 1
    2 3 3 3
    2 5 1 6
    3 1 4 1
    3 4 7 5
    2 3 4 3 2 2
    4 7

    Como vemos en las posiciones 1,2; 1,3 y 3,2 de la matriz de peso, hubo cambios y
    como habamos fijado k =4, entonces en las mismas posiciones se generarn cambios
    en la matriz de nodos intermedios, y como ya completamos las 4 iteraciones, estas
    son las matrices con los pesos ptimos y sus respectivos caminos.

    También podría gustarte