Hack x Crack - Comunidad de Seguridad informática

Programación => C / C++ => Mensaje iniciado por: SLACE en Febrero 14, 2012, 03:26:46 am

Título: Ayuda con implementacion de Dijkstra en C
Publicado por: SLACE en Febrero 14, 2012, 03:26:46 am
Entiendo como funciona dijkstra que da el camino con menor costo entre dos vertices  pero al pasarlo a codigo en C no me funciona de la manera correcta a veces termino repitiendo vertices que se encuentran añadidos ya en my lista de vertices de sugerencia.
Lo que he hecho es coger el grafo una lista de vertices recorrer a traves de cada vertice y en cada vertice recorrer su lista de adyacencia y agregar cada vertice a la lista que da dijkstra pero ahi es donde pasa las repeticiones de algunos vertices y controlar que añada vertices hasta que llegue un peso acumulado de hasta 100.
Pd: hay vertice de partida pero no hay vertice final imaginen una red de social que a una persona recomendarles amigos de los amigos que posee hasta que llegue a un peso acumulado de hasta 100 (dijkstra modificado).
Alguien que me pueda ayudar que entienda como implementarlo en C para que funcione adecuadamente.
Título: Re:Ayuda con implementacion de Dijkstra en C
Publicado por: piou en Febrero 14, 2012, 03:34:15 pm
¿Cómo no va a haber vértice final? El algoritmo de Dijkstra sirve para hallar el camino más corto entre dos puntos, así que DEBE haber vértice final.

Estaría bien que enseñases tu código para ver lo que has hecho, y te podemos orientar, en principio el algoritmo es perfectamente implementable y relativamente sencillo, sobre todo si como dices tenemos de primera mano la matriz de adyacencia del grafo.
Título: Re:Ayuda con implementacion de Dijkstra en C
Publicado por: SLACE en Febrero 17, 2012, 03:35:19 am
Para detallar un poco mas es que he estado trabajando en un proyecto acerca de una RED SOCIAL en C implementado con las TDAs listas grafo..etc el grafo que es una lista de vertices con su lista de adjacencia que en cada nodo esta una estructra d arcos que contien punteros a ls vertices de destino y de origen y su peso. ya poseo el grafo cargado con la lista de adjacencia en cada vertice.
Mi problema es en una parte del programa un modulo para SUGERIR AMIGOS a un usuario un (vertice en el grafo) sugerir los amigos de los que el usuario ya es pero solo sugerir hasta que acumule un valor de <100 por ejemplo recomendarle a al usuario A
A es amigo de: B (con un peso de 50) y C(con un peso de 20) ... B es amigo de: F (con un peso de 90)... C es amigo de: F (con un peso de 50)... y F es amigo de: H(con un peso de 28)
con este pequeño ejemplo la sugerencia para A seria F,H se le recomienda a F porque es amigo de C y acumula un valor 20+50 (y no porque es amigo de B porque acumula un valor de 50+90).. a H porque es amigo de F y acumula un valor de  20+50+28.....esto es un "pequeño ejemplo"
(dijkstra modificado) ya que obtengo el menor costo pero solo hay el vertice de origen lo otro se va recorriendo y obteniendo en el grafo..
realice un codigo pero tengo un problema obtengo usuarios (vertices) repetidos acontinuacion encontraran mi codigo ayudenme para que funcione adecuadamente
PD: las funciones como nodelistgetcont(n) y las demas son funcions de las respectivas TDAs de listas grafos..etc  la que mencione es dado un nodo obtiene el contenido puntero a una estructura y todo por lo del estilo...
Código: [Seleccionar]
List *dijkstraModif(Graph*g,GVertex *vertexIni,GVertex *vertexFin,cmpfn fn)
{
List *path;
GVertex *v,*v1,*v2;
GEdge *e;
NodeList *n,*n1,*n2;
int tentative=MAX_DIST,distance=0,contr=0;
path=listNew();
graphInit(g);
v=graphSearchVertex(g,gVertexGetContent(vertexIni),fn);
//v1=graphSearchVertex(g,gVertexGetContent(vertexFin),fn);
if(v!=NULL)
listAddNode(path,nodeListNew(v));
else
return path;

for(n2=listGetHeader(gVertexGetAdjacents(v1));n2!=NULL;n2=nodeListGetNext(n2))
{
e=nodeListGetCont(n2);

if(tentative>=gEdgeGetWeight(e))
{
tentative=gEdgeGetWeight(e);
v2=gEdgeGetDestination(e);
contr=contr+tentative; //Cambio para Sugerir amigo
if(v2!=NULL && contr<=CONSTW)//Cambio para Sugerir amigo hasta una compatibilidad <= CONSTW (100)
{
/*if(v!=v2)*/
listAddNode(path,nodeListNew(v2));
/*if(v1==v2)
return path;*/
}
if(contr>CONSTW) //Cambio para Sugerir amigo
return path;
distance=tentative;
}
else
distance=distance;

}
return path;
}