Dijkstra's algorithm: Difference between revisions
→{{header|CafeOBJ}}
Line 1,498:
Ouput
1) a list of 4-tuples with each tuple represents a node N, its source, length of the
2) a list of nodes on the shortest path from a chosen start to some
Note needs a bit more work to
"
Line 1,531:
-- Main module
mod! DIJKSTRA {
-- We use two different list notations, one for esges the other for paths.
-- A four tuple used to store graph and shortest distance▼
-- start, end, edgeDist,pathDist▼
--
▲-- start, end, edgeDist,pathDist
pr(LIST(INT) *{sort List -> PathList})▼
pr(LIST(4TUPLE(CHARACTER,CHARACTER,INT,INT)) *{sort List -> EdgeList, op (_:_) -> (_:e_), op nil -> nilE})
op dijkstra___ : Int List List -> List▼
op exploreNeighbours___ : Int List List -> 4Tuple {memo}▼
ops inf finished : -> Int ▼
op currDist__ : Int List -> Int ▼
op relax__ : List List -> List ▼
op connectedTo__ : Int List -> Bool ▼
op nextNode2Explore_ : List -> 4Tuple ▼
op connectedList___ : List Int List -> List ▼
op unvisitedList__ : List List -> List ▼
op shortestPath__ : Int List -> PathList▼
op SP___ : 4Tuple 4Tuple List -> PathList ▼
vars x y z n eD pD eD1 pD1 eD2 pD2 source currentVertex startVertex : Int▼
vars graph permanent xs : List▼
op finishedC : -> Character
vars t t1 t2 : 4Tuple
vars s f z startVertex currentVertex : Character
eq inf = 500 .
eq
eq finishedC = 'X' .
-- Main dijkstra function
eq dijkstra startVertex graph permanent =
if (exploreNeighbours startVertex permanent graph) == <<
eq exploreNeighbours startVertex permanent graph = (nextNode2Explore
(relax (unvisitedList (connectedList graph startVertex permanent) permanent) permanent )) .
-- nextNode2Explore takes a list of records and returns a record with the minimum 4th element else finished
eq nextNode2Explore
eq nextNode2Explore (t1 :e
eq nextNode2Explore (t2 :e (t1 :e xs)) = if (4* t1) < (4* t2) then t1 else nextNode2Explore (t2 :e xs) fi .
-- relaxes all edges leaving y
eq relax
eq relax (<<
<< f ; s ; eD ; ((
-- Get the current best distance for a
eq currDist
eq currDist
eq connectedTo z
eq connectedTo z ((<<
(t :e (connectedList graph s permanent))
else (connectedList graph s permanent) fi .
▲eq connectedList nil source permanent = nil .
▲eq connectedList (t : graph) source permanent = if (connectedTo source permanent) then
▲ (t : (connectedList graph source permanent))
▲ else (connectedList graph source permanent) fi .
eq unvisitedList (t :e graph) permanent = if not(connectedTo (2* t) permanent) then (t :e (unvisitedList graph permanent)) else (unvisitedList graph permanent) fi .▼
▲eq unvisitedList nil permanent = nil .
▲eq unvisitedList (t : graph) permanent = if not(connectedTo (2* t) permanent) then (t : (unvisitedList graph permanent)) else (unvisitedList graph permanent) fi .
-- To get the shortest path from a start node to some end node we used the above dijkstra function.
-- From a given start to a given end we need to trace the path from the finish to the start and then reverse the output.
var
vars start end
eq SP start end
eq SP start end (currentTuple :e
-- The graph to be traversed
op DirectedRosetta : ->
eq DirectedRosetta = ( <<
<<
<<
<<
<<
<<
<<
<<
<<
-- A set of possible
ops oneStart twoStart threeStart fourStart fiveStart sixStart : ->
eq oneStart = <<
eq twoStart = <<
eq threeStart = <<
eq fourStart = <<
eq fiveStart = <<
eq sixStart = <<
} -- End module
Line 1,634 ⟶ 1,644:
open DIJKSTRA .
--> All shortest distances starting from a(1)
red dijkstra
-- Gives, where :e is the edge list separator
--
--> Shortest path from a(1) to e(5)
red reverse (SP
-- Gives, where :p is the path list separator
--
--> Shortest path from a(1) to f(6)
red reverse (SP
-- Gives, where :p is the path list separator
--
eof
</lang>
|