Dijkstra in Prolog

Question

I have been given an assignment to write an Dijkstra Shortest Path in Prolog.

First of all I don't want source or complete implementation, as I'm trying to understand code (part of evaluation would be explaining the code). I have seen a few implementations here and there, but I don't really know, how does it work.

So far I have this:

edge(1,2,12). %edge(From,To,Cost)
...
edge(1,4,13).

vertex(1,100000,nil,false).%vertex(Id, Weight, Over, Closed).
...
vertex(5,100000,nil,false).

neigh(V1, V2):-edge(V1,V2,_).

open_neigh(V1,V2):-edge(V1,V2,_),vertex(V2,_,_,P),not(P).

nearest_neighbor(From,Who,Cost):-findall(Node,neigh(From, Node),NeighL),
    nearest_in_list(From,Who,NeighL,Cost).

n_hood(From,NeighList):-findall(Node, neigh(From,Node), NeighList).

open_n_hood(From,NeighList):-findall(Node, open_neigh(From,Node), NeighList).

nearest_in_list(_,Who,[Who],_).
nearest_in_list(From,Who,[H,K|T],Cost) :-
    edge(From,H,C1),
    edge(From,K,C2),
    C1 =< C2,
    Cost is C1,
    nearest_in_list(From,Who,[H|T],Cost).

nearest_in_list(From,Who,[H,K|T],Cost) :-
    edge(From,H,C1),
    edge(From,K,C2),
    C1 > C2,
    Cost is C2,
    nearest_in_list(From,Who,[K|T],Cost).

The thing is, I have no idea how to update the info about vertices. I have tried assert/1 and retract/1 but it doesn't work. I get error that I cannot modify static procedure vertex/4.

I'm currently using SWI Prolog, but the program should work on Amzi! Prolog too, so I would like to keep it as close to basic Prolog as possible.

Thanks.

Well that either didn't work, or I used it wrong. I added it at the beggining of the file. Still the same error - cannot modify static variable.Can you provide more info about that? Also is it SWI specific or general? — jnovacho
Always get your programs working without assert first, then use it to optimize. The point of prolog is that you're not storing data. What you want is some sort of data structure which you pass as a parameter, and a function that takes in that data structure and returns a modified version of it. Then when you've got it working, use assert in such a way that doesn't change the semantics of your code (i.e. predicates succeed now iff they succeeded before) — jmite

Carles Araguz Carles Araguz · Accepted Answer · 2014-02-15T13:57:10

If you really need to update values I would suggest you use flag/3. However, as suggested in the comments, Prolog programs usually don't have "global variables" that you update through your algorithm steps.

Instead, I would suggest that you find a proper way to calculate Dijkstra costs. Note that the initial arguments in a Dijkstra algorithm are always the "not visited" nodes, a list ([a,b,c,d|...]). At every step, you update this list by "visiting" one of these nodes and updating its costs. I see a clear recursive call here!

Dijkstra in Prolog

1 Answers