Codigo Dijkstra en C

[SLACE]

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.
Alguien que me pueda ayudar que entienda como implementarlo en C para que funcione adecuadamente.

[rir3760]

Explicaciones del algoritmo en seudocodigo (e incluso código fuente en C o C++) lo puedes encontrar en la red, por ejemplo en Wikipedia.

En mi opinión lo mejor que puedes hacer es reducir la generación del grafo a un mínimo. El siguiente paso es crear una función para el calculo de las distancias mas cortas en base a ese algoritmo.

Reducelo, publicalo y trataremos de ayudarte.

Un saludo

[TheMaker]

Representa el grafo mediante una matriz cuadradad de tamaño n=número de nodos del grafo, en la posicion matriz[k][j] pones la distancia de ir del nodo k al j, si no existe caminos entre nodos pones algún valor especial a ese camino(PE:-1) luego si matriz[k][j]>matriz[k][v]+matriz[v][j] entonces matriz[k][j]=matriz[k][v]+matriz[v][j], donde v va tomando el valor de el resto de nodos del grafo, por supuesto antes de hacer la comparacion se ha de comprobar que tanto matriz [k][v] como matriz[v][j] no son negativos(ya que habíamos dicho que representariomos que un camino no existe dandole el valor -1) lo suyo sería poniendole valor infinito(que es como lo ponen en los libros de teoria) pero claro que yo sepa c no tiene forma de representar el valor abstracto de infinito

[SLACE]

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
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] Expandir

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;
}