[Minmind]

Hola a todos. Estoy realizando en C++ un problema sobre grafos, en el cual he optado por usar el algoritmo de Floyd.

El enunciado viene a decir lo siguiente: tenemos un mapa de carreteras entre ciudades y se ha de calcular lo siguiente: el nombre de la ciudad que es el centro del país y la suprema para la ciudad central. La suprema de una ciudad a otra es el máximo valor de los caminos mínimos que llegan a (o salen de) esa ciudad y el centro es la ciudad que tiene la menor suprema. Si existe más de una solución óptima, se debe elegir aquella ciudad cuyo nombre sea alfabéticamente menor y se supone que existe siempre algún camino entre cada par de ciudades del país.

Hasta el momento llevo realizado el siguiente código, pero todavía me faltan detalles para corregir algunos errores de compilación y determinar el centro. Me he quedado un poco estancado tras lo ya realizado y agradecería si me pueden echar una mano.

#include <iostream>
#include <string.h>
#include <stdlib.h>
#define numVer 8
#define INF 100000000000
#define MAX_NOD 26
using namespace std;

int nod;
int naris;
bool G[MAX_NODOS][MAX_NODOS];
bool visitado[MAX_NODOS];
int D[numVer][numVer];
int P[numVer][numVer];

void obtenerCamino (int x, int y) {
    if (P[ x ] [y] == y) {
        cout << y << endl;
        return;
    }
    obtenerCamino(x, P[ x ] [y]);
    cout << y << endl;
}

void leeGrafo (void)
{
  cin >> nod >> naris;
  if (nod<0 || nod>MAX_NOD) {
    exit(0);
  }
    memset(G, 0, sizeof(G));
    char a, b;
    for (int i= 0; i<naris; i++) {
    cin >> a >> b;
    G[a-'A'][b-'A']= true;
  }
}

void escribeGrafo() {
    for (int i=0; i<numVer; i=i+1) {
        for (int j=0; j<numVer; j=j+1) {
            if (D[j] != INF) {
                cout << D[j] << endl;
                obtenerCamino(i,j);
                cout << endl;
            }
            else {
                continue;
            }
        }
        cout << endl;
    }

}

void floyd () {
    int i;
    int j;
    int k;

    for (int i=0; i<numVer; i=i+1) {
        for (int j=0; j<numVer; j=j+1) {
            D[j] = G[j];
            P[j] = i;
        }
    }

    for (int k=0; k<numVer; k=k+1) {
        for (int i=0; i<numVer; i=i+1) {
            for (int j=0; j<numVer; j=j+1) {
                if (D[k] + D[k,j] < D[j]) {
                    D[j] = D[k] + D[k][j];
                    P[i,j] = k;
                }
            }
        }
    escribeGrafo();
    }

    int main (void) {
        int cas;
        cin >> cas;
        for (int i= 0; i<cas; i++) {
            leeGrafo();
            floyd();
        }
    }
}

Muchas gracias por su atención. Un saludo.

[martiniano]

Hola.

Me parece buena idea utilizar el algoritmo de Floyd. Después de pasarle la matriz de pesos de las aristas del grafo puedes buscar en la matriz resultante cuál es la ciudad, o ciudades que cumplen lo pedido. Pero...

¿El código que llevas no te da errores de compilación? ¿Has probado que el programilla que te realiza el algoritmo de Floyd hace lo que toca? Me extraña mucho que C++ pille sentencias del estilo \[ D[j] =D[k] +D[k] [j]  \].

Tampoco entiendo qué querías conseguir con asignaciones como \[ D[j] =G[j]  \] cuando \[ G \] es un array bidimensional de bools y \[ D \] lo es de ints. Muy raro...

Por otro lado, tal vez sería bueno que nos contases cuál es la razón de ser de cada una de las variables que declaras globalmente. Vislumbro que en \[ D \] quieres meter luna matriz con los pesos de las aristas del grafo, pero lo demas ni idea.

Por cierto, a raíz de algunas de las conversaciones que mantuvimos por privado abrí este hilo en el que subí un código en C++ con diversos algoritmos sobre grafos. Tal vez te interese.

Un saludo.

Enlace corregido.

[Minmind]

Sí, así es. He visto que me da errores de compilación. Soy novato en C++ y no sé muy bien por qué.

Cierto, no es correcto. En esa sentencia quiero inicializar la matriz que dará la solución al grafo que se nos dé. He pensado que puedo pasar una variable graph[][numVer] como parámetro y así tendría D [ i ] [j] = graph [ i ] [j] (el primer corchete se ha escapado antes).

Claro, te cuento. P es la matriz que uso para trazar las rutas, mientras que D es la de distancias (guarda la distancia más corta entre todos los pares de vértices). G es la matriz de adyacencia y visitado son las marcas de nodos visitados.

Sí, le eché un vistazo para ayudarme también con el algoritmo de Dijkstra. Por cierto, me parece que has adjuntado al link a este tema, no a tu publicación en sí.

[martiniano]

Hola.

Antes de nada, comentarte que la mayoría de veces que entro en el foro lo hago desde máquinas desde las que no puedo programar en C, así que estaría bien que indicases qué errores te da y esas cosas.

Pues, ¿qué te parece si vamos por partes? Lo primero sería leer un grafo del teclado.

void leeGrafo (void)
{
  cin >> nod >> naris;
  if (nod<0 || nod>MAX_NOD) {
    exit(0);
  }
    memset(G, 0, sizeof(G));
    char a, b;
    for (int i= 0; i<naris; i++) {
    cin >> a >> b;
    G[a-'A'][b-'A']= true;
  }
}

Bien. Pides el número de vértices y el de aristas. Compruebas que el usuario no la ha líado antes de empezar. Hasta aquí parece que todo bien. Seguimos.

La verdad es que no estoy muy acostumbrado a usar la función memset, pero me extrañaría que el compilador te pillase esa línea. Supongo que quieres inicializar la matriz con todo ceros, pero G es un matriz de bools, entonces... No sé... Supongo que lo interesante sería inicializarla a false... Si no consigues hacerlo con memset utiliza los dos típicos bucles anidados y listo.

Lo de restar 'A' a los índices de la matriz tiene que arrojar errores por todos lados, ¿cuál es tu intención al hacerlo?

Después otra cosa, ¿no sería lo suyo aprovechar aquí para pedir aquí la matriz D?

Y una más, ¿lo de utilizar variables globales es porque te han dicho que lo hagas así o forma parte de tu estilo al programar? ¿Has oído hablar de estructuras, o de programación orientada a objetos?

Un saludo.

[Minmind]

La función memset no me da fallo, y tampoco leeGrafo en general, el problema es que tengo que reescribir el código que he puesto arriba porque me he dado cuenta de que esta función no me sirve para el problema (había supuesto erróneamente que tenía que utilizarla igual). En unas horas lo subiré nuevamente y con menos errores espero 

Tengo que hacerlo así, conozco algo de Programación Orientada a Objetos, pero en Java no en C++.

[Minmind]

Este es el nuevo código que he utilizado, ayudándome de cosas que he investigado. Ya se corrige el error de comparación que me mencionaste, aunque todavía me faltaría imprimir la suprema y el nombre de la ciudad para completar mi ejercicio, lo cual no sé muy bien si tengo que hacerlo en procedimientos aparte o dentro de lo que tengo (supongo que esto último). Cualquier indicación la agradecería.



#include <iostream>
using namespace std;

#define INF 100000
#define V 4

void escribesolucion(int dist[][V])
{
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[j] == INF)
                cout<<"INF"<<" ";
            else
                cout<<dist[j]<<" ";
        }
        cout<<endl;
    }
}


void floydWarshall (int graph[][V])
{
    int dist[V][V];
    int i;
    int j;
    int k;
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[j] = graph[j];

    for (k = 0; k < V; k++)
    {
        for (i = 0; i < V; i++)
        {
            for (j = 0; j < V; j++)
            {
                if (dist[k] + dist[k][j] < dist[j])
                    dist[j] = dist[k] + dist[k][j];
            }
        }
    }
    escribesolucion(dist);
}


int main()
{
    int graph[V][V];
    floydWarshall(graph);
    return 0;
}

[martiniano]

Hola.

He compilado tu código y me saltan los siguientes errores al compilar, en las líneas 35 y 44.



Igualmente, aun compilando bien eso no quiere decir que el programa funcione. Puede dar errores al ejecutar. De hecho, es de agradecer que el compliador te muestre errores antes de ejecutar. Y aunque no dé errores al ejecutar puede pasar que el programa no haga lo que tienes en mente.

Yo empezaría pidiéndole un grafo al usuario y visualizando la información por pantalla. Cuando el código haga eso bien, y se hayan hecho varias pruebas y eso podremos seguir avanzando.

Un saludo.