Dijkstra's algorithm: Difference between revisions
Content added Content deleted
Line 1,702: | Line 1,702: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
An imlementation of Dijkstra's algorithm in 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. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
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. |
|||
⚫ | |||
<lang 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 |
|||
⚫ | |||
% Prolog is not good at modifying memory in place, but is quite good at |
|||
⚫ | |||
% all possible solutions. |
|||
% |
|||
⚫ | |||
⚫ | |||
% 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 |
|||
⚫ | |||
% and distance from the origin. |
|||
:-dynamic |
:-dynamic |