Título: Codigo Dijkstra en C Publicado por: SLACE 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. Título: Re: Codigo Dijkstra en C Publicado por: rir3760 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 Título: Re: Codigo Dijkstra en C Publicado por: TheMaker 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
Título: Re: Codigo Dijkstra en C Publicado por: SLACE 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) |