elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: (TUTORIAL) Aprende a emular Sentinel Dongle By Yapis


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Codigo Dijkstra en C
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Codigo Dijkstra en C  (Leído 13,160 veces)
SLACE

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Codigo Dijkstra en C
« en: 14 Febrero 2012, 03:19 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.
Alguien que me pueda ayudar que entienda como implementarlo en C para que funcione adecuadamente.


En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: Codigo Dijkstra en C
« Respuesta #1 en: 15 Febrero 2012, 00:44 am »

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


En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
TheMaker


Desconectado Desconectado

Mensajes: 514



Ver Perfil
Re: Codigo Dijkstra en C
« Respuesta #2 en: 15 Febrero 2012, 03:51 am »

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
« Última modificación: 15 Febrero 2012, 03:53 am por TheMaker » En línea

Gibe money please or I report you
SLACE

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: Codigo Dijkstra en C
« Respuesta #3 en: 17 Febrero 2012, 03:18 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
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:
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;
}

En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Algoritmo de Dijkstra en Visual Basic
Programación Visual Basic
laukibuk 4 13,337 Último mensaje 17 Enero 2008, 07:32 am
por cobein
Algoritmo para un ejercicio; ¿Doble dijkstra?
Programación General
astinx 2 3,439 Último mensaje 16 Febrero 2012, 19:27 pm
por astinx
Matriz de distancias y Dijkstra
Programación General
xiruko 1 2,571 Último mensaje 12 Diciembre 2015, 13:38 pm
por SnzCeb
Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c
Programación C/C++
axel19 1 2,232 Último mensaje 3 Junio 2018, 10:23 am
por MAFUS
Algoritmo de Dijkstra
Programación C/C++
castrokin 1 3,606 Último mensaje 6 Agosto 2021, 09:15 am
por fzp
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines