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++:
#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:
Da la siguiente salida:
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
Autor
En línea
