Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|PicoLisp}}
No edit summary |
|||
Line 1,699:
Output:
<pre>-> 20</pre>
=={{header|Prolog}}==
An imlementation of Dijkstra's algorithm in Prolog
<lang prolog>%___________________________________________________________________________
%______________________________________________________________________
% Dijkstra's algorithm starts with a set of all unvisited nodes,
% assigning an initial distance value for each as infinite. It
% attempts to minimise the distance for each node from the
% origin.
% Starting at the origin (distance 0), the algorithm checks each
% neighbor's distance value and if larger than the current path
% distance, replaces the neighboring node's distance value. It then
% marks the current node as visited, and repeats the process for each of
% the neighbors. When the current node becomes the destination, the
% distance to the origin is known.
%
% This implementation is a slight variation on Dijkstra, which lends
% itself to Prolog's strengths while retaining algorithmic equivalence.
% Prolog is not good at modifying memory in place, but is quite good at
% handling facts, pattern matching, recursion and backtracking to find
% all possible solutions.
%
% A dynamic database predicate, namely
% 'rpath([target|reversed_path], distance)'
% stores the currently known shortest distance and best path to a
% destination from the origin. Since the path is a reversed list, the
% first item in the list is the destination node, and the predicate is
% efficiently matched.
% Instead of using unvisited flags on nodes, we test whether neighbors
% are already in the traversed path. This achieves the same thing as
% 'visited' flags, but in a way that is more efficient for Prolog.
%
% After the graph traversal is complete, we are left with a single
% rpath/2 predicate for each reachable node, containing the shortest path
% and distance from the origin.
:-dynamic
rpath/2. % A reversed path
edge(a,b,7).
edge(a,c,9).
edge(b,c,10).
edge(b,d,15).
edge(c,d,11).
edge(d,e,6).
edge(a,f,14).
edge(c,f,2).
edge(e,f,9).
path(From,To,Dist) :- edge(To,From,Dist).
path(From,To,Dist) :- edge(From,To,Dist).
shorterPath([H|Path], Dist) :- % path < stored path? replace it
rpath([H|T], D), !, Dist < D, % match target node [H|_]
retract(rpath([H|_],_)),
writef('%w is closer than %w\n', [[H|Path], [H|T]]),
assert(rpath([H|Path], Dist)).
shorterPath(Path, Dist) :- % Otherwise store a new path
writef('New path:%w\n', [Path]),
assert(rpath(Path,Dist)).
traverse(From, Path, Dist) :- % traverse all reachable nodes
path(From, T, D), % For each neighbor
not(memberchk(T, Path)), % which is unvisited
shorterPath([T,From|Path], Dist+D), % Update shortest path and distance
traverse(T,[From|Path],Dist+D). % Then traverse the neighbor
traverse(From) :-
retractall(rpath(_,_)), % Remove solutions
traverse(From,[],0). % Traverse from origin
traverse(_).
go(From, To) :-
traverse(From), % Find all distances
rpath([To|RPath], Dist)-> % If the target was reached
reverse([To|RPath], Path), % Report the path and distance
Distance is round(Dist),
writef('Shortest path is %w with distance %w = %w\n',
[Path, Dist, Distance]);
writef('There is no route from %w to %w\n', [From, To]).
</lang>
for example:
<pre>?- go(a,e).
New path:[b,a]
New path:[c,b,a]
New path:[d,c,b,a]
New path:[e,d,c,b,a]
New path:[f,e,d,c,b,a]
[f,c,b,a] is closer than [f,e,d,c,b,a]
[e,f,c,b,a] is closer than [e,d,c,b,a]
[d,b,a] is closer than [d,c,b,a]
[c,a] is closer than [c,b,a]
[d,c,a] is closer than [d,b,a]
[e,d,c,a] is closer than [e,f,c,b,a]
[f,c,a] is closer than [f,c,b,a]
[e,f,c,a] is closer than [e,d,c,a]
Shortest path is [a,c,f,e] with distance 0+9+2+9 = 20
true.</pre>
=={{header|Python}}==
| |||