¿Cuáles son las aplicaciones en tiempo real del algoritmo de Warshall y Floyd? Desarrollador de registros, desarrollo de aplicaciones

El algoritmo Floyd – Warshall puede usarse para resolver los siguientes problemas, entre otros:

Trayectos más cortos en gráficos dirigidos (algoritmo de Floyd).
Cierre transitivo de gráficos dirigidos (algoritmo de Warshall). En la formulación original del algoritmo de Warshall, el gráfico no está ponderado y está representado por una matriz de adyacencia booleana. Luego, la operación de suma se reemplaza por la conjunción lógica (AND) y la operación mínima por la disyunción lógica (OR).
Encontrar una expresión regular que denote el lenguaje regular aceptado por un autómata finito (algoritmo de Kleene)
Inversión de matrices reales (algoritmo de Gauss-Jordan).
Enrutamiento óptimo. En esta aplicación, uno está interesado en encontrar el camino con el flujo máximo entre dos vértices. Esto significa que, en lugar de tomar mínimos como en el pseudocódigo anterior, uno toma máximos. Los pesos de los bordes representan restricciones fijas en el flujo. Los pesos del camino representan cuellos de botella; entonces la operación de adición anterior es reemplazada por la operación mínima.
Prueba de si un gráfico no dirigido es bipartito.
Cálculo rápido de redes Pathfinder.
Rutas de ancho de banda máximo en redes de flujo

Permítanme explicar o describir el algoritmo Floyd-Warshall para encontrar la ruta más corta entre todos los nodos en un gráfico. Doy una prueba informal y proporciono una implementación en C.

Caminos más cortos

La ruta más corta entre dos nodos de un gráfico es una secuencia de nodos conectados, de modo que la suma de los bordes que los interconectan es mínima.

Toma este gráfico,

Hay varios caminos entre A y E :

Ruta 1: A -> B -> E 20
Ruta 2: A -> D -> E 25
Ruta 3: A -> B -> D -> E 35
Ruta 4: A -> D -> B -> E 20

Hay varias cosas que notar aquí:

Puede haber más de una ruta entre dos nodos
El número de nodos en la ruta no es importante (la ruta 4 tiene 4 nodos pero es más corta que la ruta 2 , que tiene 3 nodos)
Puede haber más de una ruta de longitud mínima

Algo más que debería ser obvio en el gráfico es que cualquier camino que valga la pena considerar es simple. Es decir, solo atraviesas cada nodo una vez .

Por desgracia, este no es siempre el caso. El problema aparece cuando permite bordes de peso negativos. Esto no es malo en sí mismo. Pero si aparece un ciclo de peso negativo , entonces no hay camino más corto . Mira este ejemplo:

Mira el camino B -> E -> D -> B. Este es un bucle, porque el nodo inicial es también el final. ¿Cual es el costo? Son 10-20 + 5 = -5 . Esto significa que agregar este ciclo a una ruta una vez reduce el costo de la ruta en 5 . Agregarlo dos veces reduciría el costo en 2 * 5 = 10 . Entonces, sea cual sea el camino más corto que haya encontrado, puede hacerlo más pequeño pasando por el ciclo una vez más. Por cierto, no hay problema con una ruta de costo negativo.

El algoritmo de Floyd-Warshall

Este algoritmo calcula la longitud de la ruta más corta entre todos los nodos de un gráfico en O (V

) hora. Tenga en cuenta que en realidad no encuentra los caminos, solo sus longitudes.

Digamos que tiene la matriz de adyacencia de un gráfico. Suponiendo que no haya un bucle de valores negativos, en este punto tiene la distancia mínima entre dos nodos que están conectados por un borde.

A B C D E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0

El gráfico es el que se muestra arriba (el primero).

La idea es tratar de interspace A entre dos nodos con la esperanza de encontrar una ruta más corta.

A B C D E
A 0 10 0 5 0
B 10 0 5 5 10
C 0 5 0 0 0
D 5 5 0 0 20
E 0 10 0 20 0

Luego intente intercalar B entre dos nodos:

A B C D E
A 0 10

15 5

20
B 10 0 5 5 10
do

15 5 0 10

15
D 5 5

10 0

15
mi

20 10 15 15 0

Haz lo mismo para C :

A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

Haz lo mismo para D :

A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

Y para E :

A B C D E
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0

Este es el algoritmo real:

# dist(i,j) is "best" distance so far from vertex i to vertex j # Start with all single edge paths. For i = 1 to n do For j = 1 to n do dist(i,j) = weight(i,j) For k = 1 to n do # k is the `intermediate' vertex For i = 1 to n do For j = 1 to n do if (dist(i,k) + dist(k,j) < dist(i,j)) then # shorter path? dist(i,j) = dist(i,k) + dist(k,j)

El programa

Aquí está el código en C ():

#incluir

int n; / * Entonces número de nodos * /
int dist [16] [16]; / * dist [i] [j] es la longitud del borde entre i y j si
existe o 0 si no existe * /

vacío printDist () {
int i, j;
printf (“”);
para (i = 0; i <n; ++ i) printf ("% 4c", 'A' + i); printf ("\ n"); para (i = 0; i <n; ++ i) {printf ("% 4c", 'A' + i); para (j = 0; j <n; ++ j) printf ("% 4d", dist [i] [j]); printf ("\ n"); } printf ("\ n"); } / * floyd_warshall () después de llamar a esta función dist [i] [j] será la distancia mínima entre i y j si existe (es decir, si hay una ruta entre i y j) o 0, de lo contrario * / void floyd_warshall () {int i, j, k; para (k = 0; k <n; ++ k) {printDist (); for (i = 0; i <n; ++ i) for (j = 0; j <n; ++ j) / * Si i y j son nodos diferentes y si las rutas entre i y k y entre k y j exista, haga * / if ((dist [i] [k] * dist [k] [j]! = 0) && (i! = j)) / * Vea si no puede obtener un camino más corto entre i y j intercalando k en algún lugar a lo largo de la ruta actual * / if ((dist [i] [k] + dist [k] [j] <dist [i] [j]) || (dist [i] [j] == 0)) dist [i] [j] = dist [i] [k] + dist [k] [j]; } printDist (); } int main (int argc, char * argv []) {ARCHIVO * fin = fopen ("dist.txt", "r"); fscanf (fin, "% d", & n); int i, j; para (i = 0; i <n; ++ i) para (j = 0; j <n; ++ j) fscanf (fin, "% d", & dist [i] [j]); fclose (aleta); floyd_warshall (); devuelve 0; } [/código fuente]

Espero eso ayude.

Desarrollo webProgramación informáticatiempo