Aprender a programar > C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más

Algoritmo de Floyd-Warshall

(1/1)

castrokin:
saludos a todos

tengo una consulta.

se me pide realizar un programa en C++ para encontrar, aplicando el algoritmo de Floyd-Warshall, las rutas que debería utilizar S (nodo central), para comunicarse con todas las sedes. Si se sigue asumiendo que la tasa de generación de paquetes es la misma para todas las oficinas, calcule ¿cuál es el número medio de enlaces que necesita un paquete cualquiera?



este es el codigo el cual compila pero al ejecutar crashea. su ayuda seria muy apreciada


--- Código: ---#include <iostream>
#include <climits>

using namespace std;

const int N = 4; // Nodos: S (0), 1 (1), 2 (2), 3 (3)

void floydWarshall(int adjMatrix[N][N], int dist[N][N], int pred[N][N]) {
    // Inicializar distancias y predecesores
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N; j++) {
            dist[i][j] = adjMatrix[i][j];
            if (i != j && adjMatrix[i][j] != INT_MAX) {
                pred[i][j] = i;
            } else {
                pred[i][j] = -1;
            }
        }
    }

    // Aplicar Floyd-Warshall
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pred[i][j] = pred[k][j];
                }
            }
        }
    }
}

int countHops(int pred[N][N], int start, int end) {
    if (start == end) return 0;
    if (pred[start][end] == -1) return -1; // No hay ruta

    int hops = 0;
    int current = end;
    while (current != start) {
        current = pred[start][current];
        hops++;
        if (current == -1) return -1; // Ruta interrumpida
    }
    return hops;
}

int main() {
    int adjMatrix[N][N] = {
        {0,   9,   7,   1},  // S
        {1,   0,   2,   5},  // 1
        {9,   2,   0,   2},  // 2
        {7,   5,   2,   0}   // 3
    };

    int dist[N][N];
    int pred[N][N];

    floydWarshall(adjMatrix, dist, pred);

    // Calcular número medio de enlaces desde S (nodo 0)
    double totalHops = 0;
    int numDestinos = 3; // Destinos: 1, 2, 3

    cout << "Rutas desde S:" << endl;
    for (int j = 1; j < N; j++) {
        int hops = countHops(pred, 0, j);
        if (hops != -1) {
            cout << "S -> " << j << ": " << hops << " enlaces" << endl;
            totalHops += hops;
        }
    }

    double promedio = totalHops / numDestinos;
    cout << "\nNúmero medio de enlaces: " << promedio << endl;

    return 0;
}
--- Fin del código ---

muchas gracias a todos

YoanPupo:
A primera vista no veo problemas, te aconsejo agregar codigo depurador, algunos cout<< que te avisen hasta donde avanza la ejecucion antes de fallar.
Algo como
cout<<"bucle de inicializacion terminado"<<endl;
y similares por todo el codigo, termina cada cout con endl, si no el mensaje podria no verse debido al error

Navegación

[0] Índice de Mensajes