Inicializar matrices en Floyd

[Archivel]

Hola, aunque quizá esto tiene más que ver con las matematicas que la programacion en si, estoy implementando un TAD grafo y se me plantea una duda.

Tengo que programar el algoritmo de Floyd para que me de la matriz de distancias (esto ok) y la matriz de nodos.

Os expongo graficamente mi duda con la matriz de nodos, que no se me da muy bien explicarme:



Como debo inicializar las casillas de la matriz en las que pongo interrogacion?? Al no haber un camino directo entre esos nodos, no tengo claro como iniciarlizarlas y no he encontrado ningun ejemplo que me lo aclare.

Gracias por vuestra ayuda!

[ghastlyX]

Supongo que por matriz de nodos te referirás a la matriz que te permita reconstruir cada camino mínimo. Si esto es lo que te refieres, la forma típica de hacerlo es que una vez acabado el algoritmo, la posición M(i,j) de la matriz te diga el penúltimo nodo del menor camino de i a j, llamémosle k, para luego consultar M(i,k) y así hasta llegar al nodo i.

Para ello, normalmente se inicializa poniendo lo que quieras entre nodos que no tengan aristas (puesto que si hay un camino se sobreescribirá y si no lo hay lo verás en la matriz de distancias, por lo que ignorarás lo que tengas en esta).

En tu ejemplo, la matriz de distancias inicial sería así:
0 3 INF
3 0 5
INF 5 0

Y la matriz de antecesores sería:
A A X
B B B
X C C

Donde X quiere decir que puedes poner lo que quieras.

Si no me he equivocado al picarlo rápido, el código sería así en C++:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1000000000;

int main() {
    int n, m; //nodos, aristas
    cin >> n >> m;
    vector<vector<int> > G(n, vector<int> (n, INF)); //Matriz de distancias
    vector<vector<int> > A(n, vector<int> (n, -1)); //Matriz de antecesores
    for (int i = 0; i < n; ++i) G[i][i] = 0;
    for (int i = 0; i < n; ++i) A[i][i] = i;
    for (int i = 0; i < m; ++i) { //Lectura de aristas
        int a, b, c; //extremos y coste
        cin >> a >> b >> c;
        G[a][b] = G[b][a] = c;
        A[a][b] = a;
        A[b][a] = b;
    }
    cout << "Estado inicial de las matrices" << endl;
    cout << "Matriz de distancias:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << G[i][j] << '\t';
        }
        cout << endl;
    }
    cout << "Matriz de antecesores:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << A[i][j] << '\t';
        }
        cout << endl;
    }
    //Floyd-Warshall
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (G[i][j] > G[i][k] + G[k][j]) {
                    G[i][j] = G[i][k] + G[k][j];
                    A[i][j] = A[k][j];
                    A[j][i] = A[k][i];
                }
            }
        }
    }
    cout << endl;
    cout << "Estado final de las matrices" << endl;
    cout << "Matriz de distancias:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << G[i][j] << '\t';
        }
        cout << endl;
    }
    cout << "Matriz de antecesores:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << A[i][j] << '\t';
        }
        cout << endl;
    }
}


Y ejecutándolo con tu grafo (cambiando los nombres de los nodos, en vez de A B C, 0 1 2), es decir, poniendo como entrada:

Código [Seleccionar] Expandir

3 2
0 1 3
1 2 5
Da la siguiente salida:

Código [Seleccionar] Expandir

Estado inicial de las matrices
Matriz de distancias:
0       3       1000000000
3       0       5
1000000000      5       0
Matriz de antecesores:
0       0       -1
1       1       1
-1      2       2

Estado final de las matrices
Matriz de distancias:
0       3       8
3       0       5
8       5       0
Matriz de antecesores:
0       0       1
1       1       1
1       2       2

[Archivel]

Hola,

En primer lugar lo siento por no haber contestado antes, se me juntan los ultimos dias del curro de verano con las asignaturas de septiembre y voy agobiadisima.

Probé el código (mil gracias ghastlyX) y pude adaptarlo a mi problema a las mil maravillas.

Mi codigo chequea el grafo para saber el numero de nodos y entre cuales de ellos existe arista y cual es su peso. A partir de ahi calcula las dos matrices a la perfeccion 

Solo me queda una duda, y es en grafos mas complejos, donde el camino puede ser mas largo (ejemplo A -> C -> D -> H) como rescato ese camino a partir de la matriz?

Gracias de nuevo y un saludo!!

[ghastlyX]

Tal y como he puesto el código, si M es la matriz de antecesores y u, v son dos nodos cualquiera tales que existe un camino entre ellos (la distancia mínima entre ellos tras hacer Floyd-Warshall no es INF), M[ u][ v] indica el penúltimo nodo del camino mínimo entre u y v. Por ejemplo, si M[ u][v] vale k, significa que el menor camino de u a v será:
u -> (camino entre u y k) -> k -> v.

Y dicho camino entre u y k naturalmente será el mínimo camino entre u y k, por lo que volviendo a consultar la matriz de antecesores podemos ir creando el camino, hasta llegar al origen. La siguiente función, te devolvería el camino mínimo entre s y t con el código anterior que puse:

Código (cpp) [Seleccionar] Expandir

void camino(int s, int t, vector<vector<int> >& A) {
    if (t != s) camino(s, A[s][t], A);
    cout << t << " ";
}

Por ejemplo, en el caso de un grafo más complejo como tú decías, si tienes el siguiente grafo (pongo la entrada como la recibe mi programa):

Código [Seleccionar] Expandir

5 7
0 1 1
0 2 4
0 3 3
1 3 1
2 3 1
2 4 1
3 4 5

Es evidente que el camino mínimo entre los nodos 0 y 4 tiene coste 4 y pasa por todos los nodos. Si llamas a la función que te he puesto:

Código (cpp) [Seleccionar] Expandir

cout << "Camino de nodo 0 a nodo 4" << endl;
camino(0, 4, A);

Devuelve la siguiente salida:

Código [Seleccionar] Expandir

Camino de nodo 0 a nodo 4
0 1 3 2 4

Que es efectivamente el camino mínimo entre 0 y 4.

[Archivel]

Gracias a ti soy una experta en matematicas!! jejejeje.

Lastima que en programacion pura aun ande un poco perdida.

El algoritmo me funciona perfectamente y adaptandolo a mi trabajo tuve un problema.

La clase Grafo con la que trabajo tiene definido el metodo Grafo::floyd() como una funcion privada que ni recibe parametros ni devuelve nada, simplemente internamente calcula las estructuras D y P y listo.

El problema me viene al implementar el metodo Grafo::camino(Nodo *origen, Nodo *destino) ya que desde ese metodo no puedo acceder a las estructuras D y P de floyd().

Alguna idea?

El codigo lo tengo totalmente planteado, salvo ese "pequeño" detalle de como acceder a las estructuras D y P desde camino.

Un saludo!


EDITO: Yo no he podido usar la libreria vector del STL, ya que tengo prohibido STL.

Lo que hice fue hacer las matrices de la siguiente manera:

Código [Seleccionar] Expandir


        int **D, **P;
        D = new int* [fils];
        for(int i=0;i<fils;i++){
                D[i] = new int [cols];
        }
        P = new int* [fils];
        for(int i=0;i<fils;i++){
                P[i] = new int [cols];
        }

[Archivel]

A veces la solución es tan obvia que pasamos de ella por sencilla.

Solo tuve que declarar D y P fuera del metodo y listo 

[Dashiel]

Aqui te dejo un codigo del algoritmo de floyd para usar facil t rapido ,,
solo te faltaria inicializar las matrices D (costo) y P (predecesores) que es muy sencilo o pasarlas como referencia ...
la cantidad es la cantidad maxima de la matriz que creastes!

Código (cpp) [Seleccionar] Expandir

Void Floyd()
   {
     for(int i=0; i< cantidad;i++)
      for(int j=0; j<cantidad; j++)
       for(int k=0; k<cantidad; k++)
     if(matriz[j][k]>(matriz[j][i]+ matriz[i][k]))
      {
        costos[j][k]=matriz[j][i]+ matriz[i][k];
        predecesor[j][k];
      }
   }



ya lo otro seria implemenar el agoritmo que busque el camino minimo usando estas matrices. Si tienes duda en esto te puedo ayudar!
saludos desde cuba