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
05-03-2006, 21:02
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
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++;
}
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
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.
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
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.
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
Marcadores