Búscalo aquí:

Dijkstra en Prolog

Añado el código en Prolog para hallar el camino más corto mediante el algoritmo de Dijkstra, espero les sirva de algo.

%Implementacion de Dijkstra
%definimos un grafo
grafo(a,c,60).
grafo(a,e,80).
grafo(b,a,30).
grafo(b,d,20).
grafo(d,e,10).
grafo(d,a,60).
grafo(c,e,50).
grafo(c,x,40).
grafo(e,f,20).
grafo(f,x,50).
grafo(x,g,30).
grafo(g,c,20).



%nodo inicial, nodo destino, distancia, ruta

%dijkstra(I,F,S,C,L), donde I es el nodo inicio,F el nodo Final,
%S la lista de nodos seleccionados, C la lista de nodos candidatos,
%L la lista de respuesta del camino y R de salida igual,L indica si
% hay camino de I a F.

dijkstra(_,_,_,[],L):- L=[].


%en el siguiente predicado se ejecuta cuando se encuentra la
%solucion: se determina la menorArista del Nodo I y se guarda
%en A el nodo ke hace posible esto, luego se verifica si es el final
% y por ultimo se agrega a la lista de salida.

dijkstra(I,F,S,_,L):- menorArista(I,A),
A==F,
append(S,A,Lista),
L = Lista.



%caso que A(nodo de menor arista) sea diferente de del nodo
%final, luego agregamos a la lista de seleccionados el nodo A y
%lo eliminamos de la lista de candidatos y llamamos de nuevo
%a la función dijkstra.

dijkstra(I,F,S,C,L):- menorArista(I,A),
A\=F, %siA es diferente de F,osea no es el nodo destino
append(S,A,Lista1),
eliminar(A,C,Lista2),
dijkstra(A,F,Lista1,Lista2,L).




menorArista(I,A):- findall(P,grafo(I,_,P),L),
menorlista(L,Menor),
grafo(I,A,Menor).





Por acá agrego las funciones extras que hago uso

%Detectar el menor elemento de una lista
menorlista([],0).
menorlista([X],X).
menorlista([X|L],X):- menorlista(L,Y),
menor(X,Y).
menorlista([X|L],Y):- menorlista(L,Y),
menor(Y,X).
menor(X,Y):- X =< Y.


%agregar un elemento al final de la lista
append([],L,[L]).
append([H|T],N,[H|S]):-append(T,N,S).



%eliminamos un elemento X de la lista
eliminar(_,[],[]):-fail.
eliminar(X,[X|R],R).
eliminar(X,[C|R],[C|R1]):- eliminar(X,R,R1).

18 comentarios:

  1. prezado Jorge, estoy necesitando de hacer un algoritmo que calcule el camino más corto como el suyo. Pero, el predicado para consulta se llama camino(Origen, Destino, Camino). donde Camino es la ruta de Origen hasta Destino, utilizando Djkstra. Creo que ajustandose el código llegaremos a esto.

    Si puede ayudarme, por favor contácteme!

    gracias, te aguardo!

    André
    andre.panm@gmail.com
    andre.panm@latinmail.com

    grafo esta en: http://www.inf.ufpr.br/apm04/Download/grafo.png
    y los enlaces en: http://www.inf.ufpr.br/apm04/Download/caminhos.png

    ResponderEliminar
  2. Me parece muy bueno el articulo, pero hice una pruebas al algoritmo con los siguientes datos:

    costo(pzo, ccs, 260).
    costo(ccs, por, 180).
    costo(ccs, pzo, 260).
    costo(pzo, mbo, 550).
    costo(mbo, ccs, 280).
    costo(pzo, val, 350).
    costo(mbo, val, 290).
    costo(por, mbo, 368).
    costo(val, por, 230).

    Y al consultar del origen pzo al destino mbo ,e da un resultado erroneo en cuanto a la ruta, debido a que tengo ruta directa y el codigo devuelve una ruta mucho mas larga y de mayor costo.

    Espero tu valioso comntario a fin de solucionar el inconveniente que posee el codigo.

    ResponderEliminar
  3. Saludos, estoy viendo el grafo que estas usando y estoy notando que tiene un ciclo:

    costo(pzo, ccs, 260).
    costo(ccs, pzo, 260).

    El error producido tal vez tenga que ver con eso, ahora no tengo instalado el SWI prolog para revisar más exhaustivamente el código, en todo caso si tuvieses un aporte será bienvenido.

    ResponderEliminar
  4. Hola Jorge, muy interesante tu blog. Afortunadamente pude llegar a el :).
    Respecto al algortimo dijkstra en prolog, me resulto notable, sin embargo estoy teniendo un problema con un algoritmo parecido.Necesito entregar el segundo camino mas corto en un grafo(conlos mismos origen y destino siempre a no ser que se cambie el grafo) donde muestre la ruta obviamente y la distancia de este; donde ademas el grafo posee las restricciones que no puede pasar por ciertos nodos( semaforos en este caso)
    Ejemplo.

    implementar programa que llame a la funcion "trayecto(origen,destino,Ruta,Dist)" y la respuesta sea el segundo camino mas corto (sin semaforos) y la distancia a recorrer.

    camino(origen,a,10).
    camino(casa,c,30).
    camino(a,b,5).
    camino(a,c,15).
    camino(a,f,20).
    camino(b,d,10).
    camino(b,origen,30).
    camino(b,destino,15).
    camino(c,destino,20).
    camino(d,e,10).
    camino(e,f,20).
    camino(f,destino,30).
    semaforo(b).
    semaforo(d).

    ?- trayecto(origen,destino,Ruta,Dist).

    Ruta = [casa,c,huevo]
    Dist = 50.

    De antemano gracias, y felicitaciones por tu blog.
    Mi email:

    j__perez@walla.com

    ResponderEliminar
  5. Gracias por el aporte, de hecho muy interesante y útil, gracias por compartirlo en este blog :D

    ResponderEliminar
  6. Fe de errata:

    casa = origen.
    huevo = destino.

    ?- trayecto(origen,destino,Ruta,Dist).

    Ruta = [origen,c,destino]
    Dist = 50.

    ResponderEliminar
  7. Muy buen codigo graxx. No obstante por casualidad no tendras alguna modificacion del Dijkstra que pudiera entregar el camino minimo siguiente ( osea la segunda ruta mas corta).

    juanprolog@yahoo.cl

    ResponderEliminar
  8. Hola, nose si es posible una ayudica..

    soy novato en esto y necesito usar disktra en un trabajo..

    como puedo usar tu ejemplo?...

    para que me retorne la ruta empleada y la distancia total de esta?.. :S

    ResponderEliminar
  9. Hola, tengo una duda ¿como lo ejecuto en swi-prolog? estoy aprendiendo, pero no encuentro la forma de que el dijkstra que propones aca me funcione.

    ResponderEliminar
  10. Hola, probando tu codigo vi que cuando voy desde b hasta g me entrega el camino mas corto, pero haciendo desde g hasta b me entrega este error.
    ERROR: Out of global stack.
    pq sucede esto??

    ResponderEliminar
  11. Hola a mi parecer el error que te da es debido a que segun la deficion que tiene jorge en su grafo, este no es bidireccional, a que me refiero con esto? que su grafo va de a hasta b, pero en la definicion no va de b hasta a, para ello se debe hacer un predicado que valide esto y asi puedas resolver tu problema.

    suponte llamas el predicado adyacencia
    adyacencia(X,Y,Z):-grafo(X,Y,Z).
    adyacencia(X,Y,Z):-grafo(Y,X,Z).

    Z en ambas lineas sería la distancia que hay de X a Y o de Y a X, es lo mismo. espero sea la respuesta que buscabas, saludos.

    ResponderEliminar
  12. HOLA soy novata en PROLOG puedes decirme cual es la entrada del codigo?? gracias

    ResponderEliminar
  13. Copias el código en un fichero de texto SIN FORMATO y lo guardas como dijkstra.pl por ejemplo. Luego ejecutas swi-prolog y compilas el programa con: consult(dijkstra).

    Te dirá que compiled true y lo ejecutas así:

    dijkstra(a,x,S,[a,b,c,d,e,f,g],L).

    En mi opinión no deberías pasarle como parámetro la lista de nodos candidatos sino que tiene que ser el propio programa el que busque. Sería interesante hacer un programa prolog que encuentre la ruta más corta entre dos estaciones de metro. Pero claro el grafo sería no dirigido y además tienes que tener en cuenta en qué linea estás y si tienes que cambiar de línea.
    Jorge te lo dejo como ejercicio.

    ResponderEliminar
  14. Saludos, Muchas gracias por tu aporte! Estoy aprendiendo prolog y estoy realizando un trabajo relacionado a la busqueda de minimal path entre punto a y b, y me ha servido mucho. Estuve probando el codigo pero no me funciona bien, por ejemplo si pongo de a-x o e-x funciona muy bien, pero si hago de a-d, se queda ciclado. La parte de "adyacente" donde deberia colocarla en el codigo?, Muchas gracias de antemano por su ayuda!

    ResponderEliminar
  15. como lo ejecuto en visual prolog 5.1 ???? soy nuevo

    ResponderEliminar
  16. como hago la consulta??? :/

    ResponderEliminar
  17. q tal amigo me pregunto como se ejecuta tu codigo en el motor de prolog ??? gracias de entemano o como lo consulto en pocas palabras

    ResponderEliminar
  18. hola jorge ,una pregunta como es que se hace la pregunta

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...