Dijkstra's algorithm: Difference between revisions
m
→{{header|CafeOBJ}}
Line 1,567:
-- Main dijkstra function
eq dijkstra startVertex graph permanent =
if
else (dijkstra startVertex graph ( ((exploreNeighbours startVertex permanent graph) :e permanent))) fi .▼
then permanent
else
▲
eq exploreNeighbours startVertex permanent graph =
Line 1,579 ⟶ 1,582:
eq nextNode2Explore nilE = << finishedC ; finishedC ; finishedI ; finishedI >> .
eq nextNode2Explore (t1 :e nilE) = t1 .
eq nextNode2Explore (t2 :e (t1 :e xs)) = if (4* t1) < (4* t2) then t1
nextNode2Explore (t2 :e xs) fi .
-- relaxes all edges leaving y
eq relax nilE permanent = nilE .
eq relax (<< s ; f ; eD ; pD >> :e xs) permanent =
if
<< f ; s ; eD ; ((currDist s permanent) + eD) >> :e (relax xs permanent) else▼
(currDist s permanent) < pD
▲ << f ; s ; eD ; pD >> :e (relax xs permanent) fi .
then
else
<< f ; s ; eD ; pD >> :e (relax xs permanent) fi .
| |||