Что происходит в коде?

@Diana_Pos · Регистрация: 14.04.2018

Студворк — интернет-сервис помощи студентам

Недавно начала изучать Haskell, и дошла до алгоритмов на графах. Идут очень тяжело. Нашла алгоритм Дейкстры, но не могу разобраться, что происходит в коде. А именно, не понятно, что передаётся в метод relax:

Haskell
1
retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)

А также, что происходит в методу retMinNode. Исходный код алгоритма:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

@Mysterious Light · 14.04.2018, 19:09

Ни одного комментария в коде. Такие люди не только сами страдают, но и другим способствуют.
Мне очень жалко своего потраченного времени, поэтому оставлю ответ ниже как есть с расшифровкой кода в самом низу, а Вам советую выкинуть этот код и найти нормальные примеры реализации алгоритма Дейкстры. Можете на этом форуме поискать, помнится мне, Catstail, KolodeznyDiver и прочие обсуждали различные реализации, которые написаны более понятно и прозрачно.

Ладно, поехали:

Haskell
1
2
3
4
5
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

Определение рекурсивное по первому аргументу. Второй аргумент также участвует в свёртке, которая обозначена функцией currDist.
Функция currDist проходится по списку visited слева направо и выбирает второй компонент u последней встречаемой пары вида (n, u), где n - аргумент функции.

relax points visited для каждой тройки (x,y,z) из points сопоставляет (y, currDist x + z) и из этих значений собирает новый список той же длины, что points. Можно переписать в виде:

Haskell
1
2
relax points visited = map (\(x,y,z) -> (y, currDist x + z)) points
  where currDist n = ...

Давайте посмотрим, где используется relax:

Haskell
1
2
relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, 
    (belongsTo source visited)], not (belongsTo y visited)] visited

Снова странная запись. Она эквивалентна

Haskell
1
relax [(x,y,z) | (x,y,z) <- adjList, belongsTo source visited, not (belongsTo y visited)] visited

и в свою очередь эквивалентна

Haskell
1
relax (if belongsTo source visited then [(x,y,z) | (x,y,z) <- adjList, not (belongsTo y visited)] else []) visited

Смотрим на определение belongsTo и видим вариацию функции elem из Prelude, а именно

Haskell
1
belongsTo x pairs = elem x (map fst pairs)

Функция retMinNode возвращает пару из списка пар arr, которая имеет минимальную вторую компоненту. Эта функция эквивалентна (нужен импорт Data.List и Data.Function)

Haskell
1
retMinNode arr = minimumBy (compare `on` snd) ((inf,inf):arr)

Переписанный и упрощенный вариант исходного кода

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import Data.List(minimumBy)
import Data.Function(on)
 
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 =
  if source `belongsTo` visited
    then retMinNode $
      relax (filter (\(x,y,z) -> not (belongsTo y visited)) adjList) visited
    else
      (inf,inf)
 
belongsTo::Int->[(Int,Int)]->Bool
belongsTo x pairs = elem x (map fst pairs)
 
-- почленно заменяет в первом списке (x,y,z) на (y, currDist x visited + z)
relax :: [(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)]
relax points visited = map (\(x,y,z) -> (y, currDist x visited + z)) points
 
-- currDist n visited ищет в visited последнюю пару вида (n,u) и возвращает u.
currDist :: Int -> [(Int,Int)] -> Int
currDist n visited =
  foldl (\acc t -> if (fst t == n) then (snd t) else acc) inf visited 
 
-- возвращает пару-элемент с минимальным вторым членом
retMinNode ::[(Int,Int)]->(Int,Int)
retMinNode arr = minimumBy (compare `on` snd) ((inf,inf):arr)

Теперь попытка угадать связь с предметной областью (теорией графов)

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import Data.List(minimumBy)
import Data.Function(on)
 
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 =
  if source `belongsTo` visited
    then retMinNode $
      relax (filter (\(x,y,z) -> not (belongsTo y visited)) adjList) visited
    else
      (inf,inf)
 
-- проверяем, что вершина есть в списке вершин с расстояниями
belongsTo::Int->[(Int,Int)]->Bool
belongsTo x pairs = elem x (map fst pairs)
 
currDist :: Int -> -- вершина
              [(Int,Int)] -> -- список пар вида (вершина, длина оптимального пути к ней)
              Int -- длина оптимального пути к данной вершине
currDist n visited =
  foldl (\acc t -> if (fst t == n) then (snd t) else acc) inf visited 
 
-- почленно заменяет в первом списке (x,y,z) на (y, currDist x visited + z)
relax :: [(Int,Int,Int)]-> -- список рёбер с весами
           [(Int,Int)]-> -- список вершин с расстояниями до старта
           [(Int,Int)] -- список вершин с расстояниями до старта через какое-либо ребро из списка рёбер
relax points visited = map (\(x,y,z) -> (y, currDist x visited + z)) points
 
-- выбираем вершину с меншин расстоянием до старта
retMinNode ::[(Int,Int)]->(Int,Int)
retMinNode arr = minimumBy (compare `on` snd) ((inf,inf):arr)

Жесть, конечно.

@Curry · 14.04.2018, 19:34

Не по теме:

Сообщение от Mysterious Light

Жесть, конечно

Эта жесть взята отсюда.
Но там, хоть куций, но комментарий. Всё равно жесть. inf = 100000, Карл!

@Catstail · 15.04.2018, 16:28

Дорогая Diana_Pos, вы неправильно ставите задачу. Изучать нужно либо алгоритм (реализацию на знакомом языке), либо язык (на примере знакомого алгоритма). Изучать незнакомый алгоритм на незнакомом языке крайне нерационально! Времени уйдет непропорционально много. Поэтому начнем с алгоритма Дейкстры. Этот алгоритм ищет кратчайшее расстояние от заданной вершины до всех остальных (в предположении, что в графе нет ребер отрицательного веса).

Пусть граф представлен матрицей смежности A, в которой элемент A[i,k] равен весу ребра i-k (если вершины i и k связаны) и бесконечности (если вершины не связаны). В качестве бесконечности можно взять достаточно большое число. Пусть массив D_i содержит расстояния от заданной вершины i до всех остальных, взятое из матрицы смежности.

Первоначально присваиваем всем элементам массива D_i[k] значения A[i,k]; Элементу D_i[i] присваиваем значение 0.

Обозначим через T совокупность вершин графа без вершины i.

Выполняем, пока T не пусто, следующие действия:

- ищем в T вершину u, для которой величина D_i[u] минимальна;
- исключаем u из T;
- для всех оставшихся вершин w из T вычисляем D_i[w]=min(D_i[w],D_i[u]+A[u,w])

Теперь попробуем реализовать это в Haskell. В качестве базовой структуры данных будем использовать списки целых.
Начнем с матрицы смежности:

Haskell
1
2
graph :: [[Int]] -- задаем исходный граф
graph = [[0,5,7,100,1,100],[5,0,100,2,100,100],[7,100,0,100,100,4],[100,2,100,0,1,2],[1,100,100,1,0,1],[100,100,4,2,1,0]]

Теперь реализуем заполнение массива (списка) D:

Haskell
1
2
startD :: [[Int]] -> Int -> [Int]
startD g n = map (\ k -> (g !! n) !! k) [0..(length g)-1]  -- D[k]=A[i,k]

И сформируем стартовое множество вершин t, состоящее из всех вершин графа, без стартовой вершины:

Haskell
1
2
startT :: [Int] -> Int -> [Int]
startT a i = filter (/= i) a  -- просто исключаем i-ю вершину

Нам понадобится функция, возвращающая длину ребра x-y. Это просто:

Haskell
1
dist g x y = (g !! x) !! y

Теперь надо научиться находить минимум списка D и номер, на котором он достигается. При этом брать только вершины,
входящие в t:

Haskell
1
2
3
opv d t n = head $ filter (\(k,p) -> k == m) s -- удаляем вершины с расстояниями, большими минимума и берем первую пару
            where s = map (\ k -> (d!!k,k)) t   -- список пар (расстояние, вершина)
                  m = minimum $ map fst s -- минимальное расстояние

Понимать этот код лучше с первой строки where: сначала s получит значение списка пар (расстояние,вершина). Затем выбирается минимальное расстояние (m). И, наконец, выбирается пара с минимальным расстоянием.

Далее нужно выполнить пересчет списка D:

Haskell
1
nextD g d t v dv = map (\ n -> if (d!!n) > dv+(dist g v n) && (elem n t) then dv+(dist g v n) else d!!n)  [0..(length g)-1]

Для всех элементов D (входящих в t) проверяется, можно ли уменьшить значение. Если да - то значение уменьшается. Иначе остается без изменения.

Теперь можно организовать сам алгоритм Дейкстры:

Haskell
1
2
3
4
5
6
dij' :: [[Int]] -> Int -> [Int] -> [Int] -> [Int]
dij' _ _ d [] = d  -- если множество t пусто - конец
dij' g n d t  = dij' g n dd tt
                where (omin,v) = opv d t n -- находим минимум
                      tt = filter (/= v) t -- удаляем вершину
                      dd =  nextD g d tt v omin   -- пересчитываем d и все это - на рек. вход.

Для удобства вызова эту функцию можно "обернуть" в удобную оболочку:

Haskell
1
2
dij :: [[Int]] -> Int -> [Int] -- граф и стартовая вершина
dij graph n = dij' graph n (startD graph n) (startT [0..(length graph)-1] n)

Для данного графа запуск выглядит так:

Haskell
1
2
3
4
5
6
*Main> dij graph 1
[4,0,8,2,3,4]
*Main> dij graph 0
[0,4,6,2,1,2]
*Main> dij graph 3
[2,2,6,0,1,2]

Граф показан на картинке...

@Curry · 17.04.2018, 21:58

Мой вариант

Кликните здесь для просмотра всего текста

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
{-# LANGUAGE RecordWildCards #-}
import Data.List (minimumBy)
import Data.Function (on)
 
type VertexNum = Int
type Dist = Int
 
data Vertex = Vertex { vNum :: VertexNum
                     , vDist   :: Dist
                     }
                     
type Vertexes = [Vertex]
                               
data Edge = Edge { eN0 :: VertexNum
                 , eN1 :: VertexNum
                 , eDist  :: Dist
                 } deriving (Show)
                 
type Graph = [Edge]
 
dijkstra :: VertexNum ->  -- исходная точка
            Graph     ->  -- список рёбер
            Vertexes -- список вершин и расстояний от исходной точки до них
dijkstra source = dij [] [Vertex source 0]
    where dij visited []      _     = visited
          dij visited weighed graph =
            let src@Vertex{vNum=srcNum,vDist=srcDst} = minimumBy (compare `on` vDist) weighed 
                mapFltr fM fF = map (\e@Edge{..} -> Vertex (fM e) (eDist + srcDst)) $ 
                                  filter ((== srcNum).fF) graph
                neighbours = mapFltr eN0 eN1 ++ mapFltr eN1 eN0
            in dij (src:visited) 
                   (vxRemove srcNum $ 
                    foldr (\v@Vertex{..} -> vxUpdate (min vDist) v) weighed neighbours )
                   (grRemove srcNum graph) 
 
vxUpdate :: (Dist -> Dist) -> Vertex -> Vertexes -> Vertexes
vxUpdate f (v@Vertex{vNum=ix}) = go []
    where go res [] = v:res
          go res (v'@Vertex{..}:vs) 
            | vNum == ix = Vertex vNum (f vDist) : (res ++ vs)   
            | otherwise  = go (v':res) vs
 
vxRemove :: VertexNum ->  Vertexes -> Vertexes
vxRemove ix = filter ((/=ix).vNum)
            
grRemove :: VertexNum -> Graph -> Graph
grRemove ix = filter (\Edge{..} -> ix /= eN0 && ix /= eN1)
 
instance Show Vertex where -- Компактное текстовое представление
    show Vertex{..} = concat [show vNum, "~", show vDist]

Граф задаётся списком рёбер, как в исходной задаче. Однако, граф не ориентированный. Для ориентированного нужно сделать некоторые упрощения.
Вместо безликих кортежей используются записи.
Используются вложенные функции с замыканиями.
Изменение списков, в основном, вынесено в функции vxUpdate, vxRemove, grRemove. Это могло бы упростить переход от списков к другим контейнерам.
Разумеется, никаких магических чисел означающих особые случаи. Для Haskell можно было бы использовать ADT, например Maybe, но и он не потребовался.

Для функции dijkstra напрашивается применение монады Writer для накопления результата - списка просмотренных вершин. Подключаю пакет mtl (можно и transformers), добавляю

Haskell
1
2
import Control.Monad
import Control.Monad.Writer

и функция dijkstra теперь выглядит так

Кликните здесь для просмотра всего текста

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dijkstra :: VertexNum ->  -- исходная точка
            Graph     ->  -- список рёбер
            Vertexes -- список вершин и расстояний от исходной точки до них
dijkstra source = execWriter . dij [Vertex source 0]
    where dij weighed graph = 
            unless (null weighed) $ do
                let src@Vertex{vNum=srcNum,vDist=srcDst} = minimumBy (compare `on` vDist) weighed 
                    mapFltr fM fF = map (\e@Edge{..} -> Vertex (fM e) (eDist + srcDst)) $
                                    filter ((== srcNum).fF) graph
                    neighbours = mapFltr eN0 eN1 ++ mapFltr eN1 eN0
                tell [src]
                dij (vxRemove srcNum $ 
                    foldr (\v@Vertex{..} -> vxUpdate (min vDist) v) weighed neighbours)
                    (grRemove srcNum graph)

Мне кажется что с монадой Writer красивее.

@Scalpel · 13.11.2018, 17:22

Добрый день,

Я новичек.
Разбираю алгоритм Декстры на Вашем примере.
Что-то не получается скомпилировать Ваш представленный код...
Я про пример уважаемого Catstail.

Добавлено через 8 минут
parse error (possibly incorrect indentation or mismatched brackets)
|
11 | startD :: [[Int]] -> [Int] -> [Int] | ^

Добавлено через 5 часов 4 минуты
Проблема была в моем редакторе. Интересно как адаптировать данный код под поиск кратчайшего пути к определенной вершине.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Scalpel 0 / 0 / 0 Регистрация: 02.01.2017 Сообщений: 17
	13.11.2018, 17:22
	Добрый день, Я новичек. Разбираю алгоритм Декстры на Вашем примере. Что-то не получается скомпилировать Ваш представленный код... Я про пример уважаемого Catstail. Добавлено через 8 минут parse error (possibly incorrect indentation or mismatched brackets) \| 11 \| startD :: [[Int]] -> [Int] -> [Int] \| ^ Добавлено через 5 часов 4 минуты Проблема была в моем редакторе. Интересно как адаптировать данный код под поиск кратчайшего пути к определенной вершине. 0