Herramientas de usuario
algoritmos-oia:grafos:floyd-warshall
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa | |||
|
algoritmos-oia:grafos:floyd-warshall [2017/12/26 19:12] sebach ↷ Page moved from algoritmos-oia:floyd-warshall to algoritmos-oia:grafos:floyd-warshall |
algoritmos-oia:grafos:floyd-warshall [2020/04/26 15:22] (actual) santo |
||
|---|---|---|---|
| Línea 21: | Línea 21: | ||
| #define forn(i,n) for(int i=0;i<int(n); i++) | #define forn(i,n) for(int i=0;i<int(n); i++) | ||
| - | struct arista{ | + | struct arista { |
| int u, v, longitud; | int u, v, longitud; | ||
| }; | }; | ||
| - | vector< vector<int> > floydWarshall(vector<arista>& grafo, int V){ | + | vector< vector<int> > floydWarshall(vector<arista>& grafo, int V) { |
| - | const int INF = 2e9; | + | const int INF = 1000000000; |
| vector< vector<int> > distancia(V, vector<int>(V, INF)); | vector< vector<int> > distancia(V, vector<int>(V, INF)); | ||
| - | forn(i, grafo.size()){ | + | forn(i, grafo.size()) { |
| arista a = grafo[i]; | arista a = grafo[i]; | ||
| distancia[a.u][a.v]=a.longitud; | distancia[a.u][a.v]=a.longitud; | ||
| Línea 34: | Línea 34: | ||
| // distancia[a.v][a.u]=a.longitud; | // distancia[a.v][a.u]=a.longitud; | ||
| } | } | ||
| - | forn(k, V){ | + | forn(k, V) { |
| - | forn(i, V){ | + | forn(i, V) { |
| - | forn(j, V){ | + | forn(j, V) { |
| distancia[i][j] = min(distancia[i][j], distancia[i][k] + distancia[k][j]); | distancia[i][j] = min(distancia[i][j], distancia[i][k] + distancia[k][j]); | ||
| } | } | ||
| } | } | ||
| } | } | ||
| - | forn(i, V){ | + | forn(i, V) { |
| - | if(distancia[i][i]<0){ | + | if(distancia[i][i]<0) { |
| cout<<"ERROR, CICLO NEGATIVO"<<endl; | cout<<"ERROR, CICLO NEGATIVO"<<endl; | ||
| } | } | ||
| Línea 51: | Línea 51: | ||
| Notar que la detección de un ciclo negativo se hace mirando $distancia[i][i]$. Si un nodo está en un ciclo negativo, entonces el algoritmo va a guardar como longitud mínima el camino desde $i$, pasando por el ciclo negativo, y volviendo a $i$, entonces hay un ciclo negativo si y sólo si hay algún nodo con $distancia[i][i]<0$ | Notar que la detección de un ciclo negativo se hace mirando $distancia[i][i]$. Si un nodo está en un ciclo negativo, entonces el algoritmo va a guardar como longitud mínima el camino desde $i$, pasando por el ciclo negativo, y volviendo a $i$, entonces hay un ciclo negativo si y sólo si hay algún nodo con $distancia[i][i]<0$ | ||
| + | |||
| + | ===== Reconstrucción de los caminos ===== | ||
| + | |||
| + | ¿Qué ocurre cuando, además de computar la distancia mínima para todo par de nodos, se desea poder obtener un camino mínimo para cualquier par dado? | ||
| + | |||
| + | Hay varias formas posibles. Explicamos a continuación una de las más simples. | ||
| + | |||
| + | La idea consiste en guardar una matriz adicional, de modo que $siguiente[i][j]$ indique cuál es el siguiente nodo luego del comienzo $i$, que se debe utilizar en el camino óptimo para ir desde $i$ hasta $j$. Es decir, sería el segundo nodo del camino, donde el primero es el propio $i$. | ||
| + | |||
| + | Inicialmente, recordemos que en la inicialización de la matriz del algoritmo de Floyd, únicamente tenemos considerados los caminos que no utilizan ningún nodo intermedio, es decir, aquellos caminos directos que llegan a destino usando una única arista a lo sumo. Por lo tanto, inicialmente tendremos $siguiente[i][j] = j$ para todos los pares $i,j$. | ||
| + | |||
| + | Además de esta inicialización, el único cambio que realizamos es que, dentro del for principal, junto con la actualización de la distancia, se actualiza quién es el siguiente al encontrar un mejor camino. | ||
| + | |||
| + | El algoritmo queda entonces: | ||
| + | |||
| + | <code cpp floyd_con_caminos.cpp> | ||
| + | |||
| + | // Aqui va la inicializacion de distancias, exactamente igual que antes. | ||
| + | vector< vector<int> > siguiente(V, vector<int>(V)); | ||
| + | forn(i,V) | ||
| + | forn(j,V) | ||
| + | siguiente[i][j] = j; | ||
| + | forn(k, V) { | ||
| + | forn(i, V) { | ||
| + | forn(j, V) { | ||
| + | int nueva = distancia[i][k] + distancia[k][j]; | ||
| + | if (nueva < distancia[i][j]) { | ||
| + | distancia[i][j] = nueva; | ||
| + | siguiente[i][j] = siguiente[i][k]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | ¿De qué nos sirve tener esta tabla adicional $siguiente$? Gracias a ella, podemos reconstruir un camino óptimo desde $i$ hasta $j$ fácilmente: iniciamos en $x=j$, y luego en cada paso nos movemos desde el nodo actual $x$ hasta $siguiente[x][j]$, parando al llegar a $j$. La secuencia de nodos utilizada forma el camino óptimo. | ||
| + | |||
| + | <code cpp print_camino.cpp> | ||
| + | // Muestra todos los nodos del camino optimo de i hasta j | ||
| + | int x = i; | ||
| + | cout << i << "\n"; | ||
| + | while (x != j) { | ||
| + | x = siguiente[x][j]; | ||
| + | cout << x << "\n"; | ||
| + | } | ||
| + | </code> | ||
| + | |||
algoritmos-oia/grafos/floyd-warshall.1514315557.txt.gz · Última modificación: 2017/12/26 19:12 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
