Resultados 1 al 8 de 8

Tema: Grafos

  1. #1 Grafos 
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    Alguien tiene algun enlace o algun fichero de ejercicios resueltos de grafos (Djikstra, Floyd, Warshall etc.) en pseudocodigo o C preferentemente? Si no, en cualquier lenguaje, es para ver un poco el funcionamiento. Saludos
    Citar  
     

  2. #2  
    Medio
    Fecha de ingreso
    Mar 2006
    Mensajes
    86
    Descargas
    0
    Uploads
    0

    Obviamente es la funcion para Dijkstra se murieron 4 neuronas por el esfuerzo para resolverlo pero he aqui : espero os entendeis solo os pido un favor: No haceis preguntas bobas al respecto OK
    void Dijkstra(int p)
    {
    int i,j,pa=p,pan,nee=0,k;
    for(j=0;j<=np;j++)
    for(i=0;i<=np;i++)
    res[i][j]=0;
    while(nee!=(np-1))
    {
    for(i=0;i<np;i++)
    {
    if(pa==p)
    res[i][nee]=matriz[i][pa];
    else
    {
    if(matriz[i][pa]&&(res[i][nee-1]==0||(matriz[i][pa]+res[pa][nee-1])<res[i][nee-1])
    &&res[i][np]!=1)
    res[i][nee]=matriz[i][pa]+res[pa][nee-1];
    else
    res[i][nee]=res[i][nee-1];
    }
    }
    res[pa][np]=1;
    j=1000,k=p;
    for(i=0;i<np;i++)
    {
    if(res[i][nee]<j&&res[i][nee]!=0&&res[i][np]!=1)
    {
    j=res[i][nee];
    k=i;
    }
    }
    pan=pa;
    pa=k;
    res[np][nee]=pan;
    nee++;
    }
    e++;
    }
    Citar  
     

  3. #3  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    Evidentemente esa no era mi pregunta, porque para conseguir el algoritmo Djikstra o cualquiera de los demas, sabria hacerlo solo; en verdad se como funciona cada uno y lo tengo programado en C y pseudocodigo. Lo que pedi es alguna aplicacion del algoritmo en algun problema real como resolucion del problema del viajante o algun problema de ese tipo (NP-complejidad) para poder hacer el analisis y ver el funcionamiento en casos de que exista alguna modificacion. Un ejemplo es el algoritmo de Floyd modificado para ver la existencia de ciclos (evidentemente no es NP). Pues eso es lo que buscaba, no implementacion de ningun algoritmo; hasta prefiero que sea en pseudocodigo
    Citar  
     

  4. #4  
    Iniciado
    Fecha de ingreso
    Aug 2006
    Mensajes
    2
    Descargas
    0
    Uploads
    0

    Saludos:

    Bueno, yo si quisiera su ayuda en cuanto a los grafos, y si tuvieras un programa que realizara un grafo, te lo agradeceria eternamente. Hazme el favor de dejar todo el codigo aqui o a mi mail, por favor.
    Citar  
     

  5. #5  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    Phhh... yo de grafos tengo unos cuantos solucionados pero son problemas tipo con lo cual no creo que haga falta que te mande todos, sino, mejor dime de que lo necesitas concretamente y asi es mas facil para todos. Saludos
    Citar  
     

  6. #6  
    Iniciado
    Fecha de ingreso
    Aug 2006
    Mensajes
    2
    Descargas
    0
    Uploads
    0
    Bueno, lo que necesito es un programa en c o c++ que haga un grafo. Ahora, que si puede hacer un recorrido por niveles, estaria mucho mejor, pero cualquiera de los dos programas me serviria de mucho.
    Citar  
     

  7. #7  
    Moderador Global Avatar de hystd
    Fecha de ingreso
    Jul 2005
    Ubicación
    1, 11, 21, 1211...
    Mensajes
    1.596
    Descargas
    58
    Uploads
    0
    Citar  
     

  8. #8  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    Bueno mira, lo siento por no escribirte antes pero no pude, asi que vamos a ver. Para crear un grafo en C o C++ tienes que elegir una representación, lo cual en C normalmente es una estructura que contendrá la matriz(de adyacencia o matriz de costes) y unos cuantos datos dependiendo de lo que crees necesario. El caso es que la creación del grafo en sí es rellenar la matriz, asi de simple. Ahora bien el recorrido de niveles (la verdad es que los que yo conozco son recorrido en anchura y altura, pero supongo que será uno de ellos) deberías intentar escribir la funcion tu solo pero si necesitas solo el codigo (lo cual no creo que seria buena idea darte proque si) ya te lo mandare en el siguiente mensaje. Saludos
    Citar  
     

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •