Since you want to find the shortest paths for all pairs of cities, isn't the Floyd-Warshall algorithm what you should be using instead of Dijkstra's? I will use Floyd-Warshall in this answer. What both algorithms have in common is that they need to make updates to some data structure. I will use the Prolog database for this, since you want to assert some dynamic facts anyway. However, the solution will be very "non-logical".
I will be using the following input graph from the Floyd-Warshall Wikipedia page:
node(1).
node(2).
node(3).
node(4).
edge(1, 3, -2).
edge(2, 1, 4).
edge(2, 3, 3).
edge(3, 4, 2).
edge(4, 2, -1).
As a commenter mentioned, a technique you can use here are failure-driven loops.
Here is what a failure-driven loop looks like:
visit_each_node :-
node(Node),
fail.
This doesn't seem to do anything:
?- visit_each_node.
false.
And indeed, logically it just fails. But procedurally it visits each node, it just doesn't do anything with it.
You can do things inside failure-driven loops, but only non-logical things like I/O, or modifications of the Prolog database. For example:
print_each_node :-
node(Node),
write('visiting '),
write(Node),
nl,
fail.
This will visit a node, print it, and come to the failure. The failure will force it to backtrack to find another node and print it. Then it will fail again, find another node, and so on, until all nodes have been visited, and finally the query fails:
?- print_each_node.
visiting 1
visiting 2
visiting 3
visiting 4
false.
We will usually want our loops to do something and then succeed. For this, we can just add another clause that succeeds:
print_each_node_and_succeed :-
node(Node),
write('visiting '),
write(Node),
nl,
fail.
print_each_node_and_succeed :-
% when we get here, all nodes have been visited
true.
This will do all of what I described above. Then, after the first clause has definitely failed, it will execute the second clause and will succeed:
?- print_each_node_and_succeed.
visiting 1
visiting 2
visiting 3
visiting 4
true.
In general, a failure-driven loop will consist of: (a) some goals that generate some data, (b) some goals that consume that data non-logically, (c) a fail, all in one clause, and (d) a second clause that succeeds:
generic_loop :-
% generate
some_x(X),
some_y(Y),
% consume
do_something_non_logical_with_x_and_y(X, Y),
% loop back
fail.
generic_loop :-
% nothing more to do
true.
Now, for the Floyd-Warshall algorithm. We'll populate the following dynamic predicate, using from_to_set_distance to encapsulate removing any old stored distance between two cities and storing a new one:
:- dynamic from_to_distance/3.
from_to_set_distance(From, To, Distance) :-
retractall(from_to_distance(From, To, _OldDistance)),
asserta(from_to_distance(From, To, Distance)).
The first step of the algorithm is to initialize all distances from given edges. This must visit all pairs of cities and do something non-logical, namely, update the Prolog database. A job for a failure-driven loop!
initialize_distances :-
retractall(from_to_distance(_From, _To, _Distance)),
node(U),
node(V),
( U = V
-> from_to_set_distance(U, U, 0)
; edge(U, V, Distance)
-> from_to_set_distance(U, V, Distance)
; Infinity = 999999,
from_to_set_distance(U, V, Infinity) ),
% failure-driven loop
fail.
initialize_distances :-
% when we get here, all pairs of nodes have been initialized
true.
The second step is to visit all triples of cities and do something non-logical: Update the stored distance if we found a shorter path than the one we had stored before. Again, a job for a failure-driven loop!
compute_pairwise_distances :-
node(K),
node(I),
node(J),
from_to_distance(I, J, DistIJ),
from_to_distance(I, K, DistIK),
from_to_distance(K, J, DistKJ),
( DistIJ > DistIK + DistKJ
-> DistIKJ is DistIK + DistKJ,
from_to_set_distance(I, J, DistIKJ)
; % nothing to do
true ),
% failure-driven loop
fail.
compute_pairwise_distances :-
% when we get here, all triples of nodes have been visited and all
% pairwise distances computed
true.
The entire Floyd-Warshall algorithm first does the initialization, then the computation of all pairwise distances:
floyd_warshall :-
initialize_distances,
compute_pairwise_distances.
When we run this, it will not produce anything visible:
?- floyd_warshall.
true.
But the database will have been updated. To see all the stored distances, we can visit all of them and do something non-logical, namely, print them. A job for... you guessed it: a failure-driven loop!
?- from_to_distance(From, To, Distance), write(from_to_distance(From, To, Distance)), nl, fail.
from_to_distance(3,2,1)
from_to_distance(3,1,5)
from_to_distance(1,2,-1)
from_to_distance(2,4,4)
from_to_distance(1,4,0)
from_to_distance(4,3,1)
from_to_distance(4,1,3)
from_to_distance(2,3,2)
from_to_distance(4,4,0)
from_to_distance(4,2,-1)
from_to_distance(3,4,2)
from_to_distance(3,3,0)
from_to_distance(2,2,0)
from_to_distance(2,1,4)
from_to_distance(1,3,-2)
from_to_distance(1,1,0)
false.
