Недавно начал изучать Haskell, и дошёл до алгоритмов на графах. Идут очень тяжело. Нашёл алгоритм Дейкстры, но не могу разобраться, что происходит в коде. А именно, не понятно, что передаётся в метод relax:
retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)
А также, что происходит в методу retMinNode. Исходный код алгоритма:
inf = 100000
dijkstra ::Int->Int->[(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)]
dijkstra s d adjList visited
| (p,q) == (inf, inf) = visited
| otherwise = dijkstra p d adjList ((p,q):visited)
where (p,q) = exploreNeighbours s visited adjList
exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int)
exploreNeighbours source visited adjList =
retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList,
(belongsTo source visited)], not (belongsTo y visited)] visited)
belongsTo::Int->[(Int,Int)]->Bool
belongsTo _ [] = False
belongsTo s ((x,_):xs)
| (x==s) = True
| otherwise = belongsTo s xs
relax :: [(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)]
relax [] visited = []
relax ((x,y,z):ns) visited = (y, (currDist x) + z):relax ns visited
where currDist n = foldl(\acc t -> if (fst t == n) then (snd t) else
acc) inf visited
retMinNode ::[(Int,Int)]->(Int,Int)
retMinNode [] = (inf,inf)
retMinNode arr = foldl (\acc t -> if ((snd t) < (snd acc)) then t else acc)
(inf,inf) arr