How to resolve the algorithm Dijkstra's algorithm step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Dijkstra's algorithm step by step in the Prolog programming language

Table of Contents

Problem Statement

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.
This algorithm is often used in routing and as a subroutine in other graph algorithms.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.

If the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road,   Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.
As a result, the shortest path first is widely used in network routing protocols, most notably:

The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of 2 or more nodes, generally represented by:

A destination node is not specified. The output is a set of edges depicting the shortest path to each destination node.

You can use numbers or names to identify vertices in your program.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Dijkstra's algorithm step by step in the Prolog programming language

Source code in the prolog programming language

%___________________________________________________________________________

:-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]).

You may also check:How to resolve the algorithm Identity matrix step by step in the REXX programming language
You may also check:How to resolve the algorithm Partition function P step by step in the Python programming language
You may also check:How to resolve the algorithm Mutual recursion step by step in the REXX programming language
You may also check:How to resolve the algorithm User input/Graphical step by step in the REXX programming language
You may also check:How to resolve the algorithm Scope/Function names and labels step by step in the Icon and Unicon programming language