|
=={{header|Prolog}}==
An imlementation of Dijkstra's algorithm in 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 :▼
%<pre> 'rpath([target|reversed_path], distance) ' </pre>▼
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
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.▼
<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
% 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
| 