CODEWITHSUNDEEP
logic-programminganswer-set-programmingclingo
user16457964
user16457964

Reputation: 11

Shortest path in Answer Set Programming

I'm trying to find all the shortest path from one source node to all other destination node (so 1-3, 1-5, 1-4) with the relative cost for each shortest path.

I've tried with this code

node(1..5).

edge(1,2,1).
edge(2,3,9).
edge(3,4,4).
edge(4,1,4).
edge(1,3,1).
edge(3,5,7).

start(1).
end(3).
end(4).
end(5).

0{selected(X,Y)}1:-edge(X,Y,W).
path(X,Y):-selected(X,Y).
path(X,Z):-path(X,Y),path(Y,Z).
:-start(X),end(Y),not path(X,Y).
cost(C):-C=#sum{W,X,Y:edge(X,Y,W),selected(X,Y)}.
#minimize{C:cost(C)}.

#show selected/2.

but my code return this answer

> `clingo version 5.6.0 (c0a2cf99)
> Reading from stdin
> Solving...
> Answer: 1
> selected(3,4) selected(1,3) selected(3,5)
> Optimization: 12
> OPTIMUM FOUND
> 
> Models       : 1
> Optimum    : yes
> Optimization : 12
> Calls        : 1
> Time         : 0.043s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
> CPU Time     : 0.000s`

What is wrong? How can I enumerate all shortest paths with relative costs?

Upvotes: 1

Views: 371

Answers (1)

logi-kal
logi-kal

Reputation: 7880

Surely an error is that you are aggregating all the costs in C but, if I have correctly understood, you need distinct costs depending on the ending node.

Then there may be also other errors, but I can't exactly understand what do you mean with that program.

I would write it as follows:

node(1..5) .

edge(1,2,1) .
edge(2,3,9) .
edge(3,4,4) .
edge(4,1,4) .
edge(1,3,1) .
edge(3,5,7) .

start(1) .
end(3) .
end(4) .
end(5) .

% For each destination E, some outgoing edge from the start node should be selected
:- start(S), end(E), not selected(S,_,E) .

% No edge pointing to the start node should be selected
:- start(S), selected(_,S,_) .

% If an edge points to the end node, then it may be (or not be) selected for reaching it
0{selected(X,E,E)}1 :- edge(X,E,_), end(E) .

% If an outgoing edge from Y has been selected for reaching E, then an incoming edge may be (or not be) selected for reaching E
0{selected(X,Y,E)}1 :- edge(X,Y,_), selected(Y,_,E) .

% Compute the cost for reaching E
cost(E,C) :- C=#sum{W : edge(X,Y,W), selected(X,Y,E)}, end(E) .
#minimize{C : cost(E,C)} .

#show selected/3 .
#show cost/2 .

The execution of the above program is as follows:

clingo version 5.3.0
Reading from test.lp
Solving...
Answer: 1
selected(3,5,5) selected(1,3,3) selected(3,4,4) selected(1,3,4) selected(1,3,5) cost(3,1) cost(4,5) cost(5,8)
Optimization: 14
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 14
Calls        : 1
Time         : 0.017s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

where:

  • an atom select(X,Y,Z) indicates that the edge (X,Y) has been selected for reaching the node Z;
  • an atom cost(E,C) indicates that the minimum cost for reaching the end node E is C.

The starting node is implicit since it is unique.

Upvotes: 1

Related Questions