Jak zaimplementować algorytm Dijkstry w Haskell

Question

Dla moich studiów muszę napisać następującą funkcję, która uzyska najkrótszą trasę między dwoma krajami. Już napisałem funkcję isRoute, która sprawdza, czy istnieje połączenie między dwoma krajami, oraz funkcję yieldRoute, która właśnie zwraca połączenie między dwoma krajami. Teraz muszę zakodować funkcję, która zwraca najkrótszą trasę między dwoma krajami.

Moje pierwsze podejście polegało na uzyskaniu wszystkich połączeń między dwoma krajami, a następnie uzyskaniu najkrótszej z nich, ale uzyskanie wszystkich połączeń jest denerwujące dla programisty w mojej opinii. Teraz wpadłem na pomysł implementacji algorytmu dijstra, ale tak naprawdę to też jest trudne. Czy możecie mi dać jakiś pomysł, jak to zrobić?

Musimy korzystać z tych rodzajów

type Country = String 
type Countries = [Country] 
type TravelTime = Integer -- Travel time in minutes 
data Connection = Air Country Country TravelTime 
    | Sea Country Country TravelTime 
    | Rail Country Country TravelTime 
    | Road Country Country TravelTime deriving (Eq,Ord,Show) 
type Connections = [Connection] 
data Itinerary = NoRoute | Route (Connections,TravelTime) deriving (Eq,Ord,Show) 

Moja funkcja trasa wydajność, która jest po prostu przeszukiwanie wszerz (nie wolno ich zmieniać, ale ofc wolno nam dodawać nowe typy.): (Sry dla niemieckich komentarzach)

-- Liefert eine Route falls es eine gibt 
yieldRoute :: Connections -> Country -> Country -> Connections 
yieldRoute cons start goal 
      | isRoute cons start goal == False = [] 
      | otherwise      = getRoute cons start [] [start] goal 

getRoute :: Connections -> Country -> Connections -> Countries -> Country -> Connections 
getRoute cons c gone visited target 
      | (c == target) = gone 
      | otherwise = if (visit cons c visited) then (getRoute cons (deeper cons c visited) (gone ++ get_conn cons c (deeper cons c visited)) (visited ++ [(deeper cons c visited)]) target) else (getRoute cons (back (drop (length gone -1) gone)) (take (length gone -1) gone) visited target) 

-- Geht ein Land zurück 
back :: Connections -> Country 
back ((Air c1 c2 _):xs) = c1 
back ((Sea c1 c2 _):xs) = c1 
back ((Rail c1 c2 _):xs) = c1 
back ((Road c1 c2 _):xs) = c1 

-- Liefert das nächste erreichbare Country 
deeper :: Connections -> Country -> Countries -> Country 
deeper ((Air c1 c2 _):xs) c visited 
      | (c1 == c) = if (c2 `elem` visited) then (deeper xs c visited) else c2 
      | (c2 == c) = if (c1 `elem` visited) then (deeper xs c visited) else c1 
      | otherwise = deeper xs c visited 
deeper ((Sea c1 c2 _):xs) c visited 
      | (c1 == c) = if (c2 `elem` visited) then (deeper xs c visited) else c2 
      | (c2 == c) = if (c1 `elem` visited) then (deeper xs c visited) else c1 
      | otherwise = deeper xs c visited 
deeper ((Rail c1 c2 _):xs) c visited 
      | (c1 == c) = if (c2 `elem` visited) then (deeper xs c visited) else c2 
      | (c2 == c) = if (c1 `elem` visited) then (deeper xs c visited) else c1 
      | otherwise = deeper xs c visited 
deeper ((Road c1 c2 _):xs) c visited 
      | (c1 == c) = if (c2 `elem` visited) then (deeper xs c visited) else c2 
      | (c2 == c) = if (c1 `elem` visited) then (deeper xs c visited) else c1 
      | otherwise = deeper xs c visited 

-- Liefert eine Connection zwischen zwei Countries 
get_conn :: Connections -> Country -> Country -> Connections 
get_conn [] _ _ = error "Something went terribly wrong" 
get_conn ((Air c1 c2 t):xs) c3 c4 
      | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)] 
      | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)] 
      | otherwise    = get_conn xs c3 c4 
get_conn ((Sea c1 c2 t):xs) c3 c4 
      | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)] 
      | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)] 
      | otherwise    = get_conn xs c3 c4 
get_conn ((Road c1 c2 t):xs) c3 c4 
      | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)] 
      | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)] 
      | otherwise    = get_conn xs c3 c4 
get_conn ((Rail c1 c2 t):xs) c3 c4 
      | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)] 
      | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)] 
      | otherwise    = get_conn xs c3 c4 

-- Überprüft ob eine besuchbare Connection exestiert 
visit :: Connections -> Country -> Countries -> Bool 
visit [] _ _ = False 
visit ((Air c1 c2 _):xs) c visited 
       | (c1 == c) = if (c2 `elem` visited) then (visit xs c visited) else True 
       | (c2 == c) = if (c1 `elem` visited) then (visit xs c visited) else True 
       | otherwise = visit xs c visited 
visit ((Sea c1 c2 _):xs) c visited 
       | (c1 == c) = if (c2 `elem` visited) then (visit xs c visited) else True 
       | (c2 == c) = if (c1 `elem` visited) then (visit xs c visited) else True 
       | otherwise = visit xs c visited 
visit ((Rail c1 c2 _):xs) c visited 
       | (c1 == c) = if (c2 `elem` visited) then (visit xs c visited) else True 
       | (c2 == c) = if (c1 `elem` visited) then (visit xs c visited) else True 
       | otherwise = visit xs c visited 
visit ((Road c1 c2 _):xs) c visited 
       | (c1 == c) = if (c2 `elem` visited) then (visit xs c visited) else True 
       | (c2 == c) = if (c1 `elem` visited) then (visit xs c visited) else True 

ten jeden mam teraz napisać:

yieldFastestRoute :: Connections -> Country -> Country -> Itinerary 

Dijkst ra Algorytm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Moje pierwsze podejście było takie: (jak mówiłem miałem problemy z getallRoutes)

yieldFastestRoute :: Connections -> Country -> Country -> Itinerary 
yieldFastestRoute cons start targ 
      |(isRoute start targ == False) = NoRoute 
      |otherwise     = (Route (getFastest (getAllRoutes cons start targ)) (sumTT (getFastest (getAllRoutes cons start targ)))) 

-- Liefert alle Routen zwischen zwei Ländern 
getAllRoutes :: Connections -> Country -> Country -> [Connections] 

-- Liefert aus einer Reihe von Connections die schnellste zurück 
getFastest :: [Connections] -> Connections 
getFastest (x:xs) = if ((sumTT x) < sumTT (getFastest xs) || null (getFastest xs)) then x else (getFastest xs) 

sumTT :: Connections -> TravelTime 
sumTT []     = 0 
sumTT ((Air _ _ t): xs) = t ++ sumTT xs 
sumTT ((Rail _ _ t): xs) = t ++ sumTT xs 
sumTT ((Road _ _ t): xs) = t ++ sumTT xs 
sumTT ((Sea _ _ t): xs) = t ++ sumTT xs 

Zasadniczo chcę wiedzieć, co jest najlepszym sposobem wdrożenia Dijkstra w Haskell, lub jeśli istnieje inne podejście, które mógłbym zastosować.

Answer 1

Nie to wspaniałe i genialne wprowadzenie do tego tematu przez: Andrew Goldberg i Simon Peyton Jones: http://www.ukuug.org/events/agm2010/ShortestPath.pdf

Pomogło mi to zrozumieć problem, przed napisaniem jakiegokolwiek kodu. Bardzo dobrze wyjaśnia algorytm Dijkstry, po czym łatwo go wdrożyć. Daje też wiele ulepszeń oryginalnego algorytmu, który najprawdopodobniej zainspiruje Cię tak bardzo, jak mnie zainspirował.

Answer 2

Wydaje się, że kodowane wielką część algorytmu

Oto projekt Martina Erwig w Haskell, które mogą pomóc, aby dać Ci kilka pomysłów

-- SP.hs -- Dijkstra's Shortest Path Algorithm (c) 2000 by Martin Erwig 
module SP (
    spTree,spLength,sp,  -- shortest paths 
    dijkstra 
) where 

import qualified Heap as H 
import Graph 
import RootPath 
expand :: Real b => b -> LPath b -> Context a b -> [H.Heap (LPath b)] 
expand d p (_,_,_,s) = map (\(l,v)->H.unit ((v,l+d):p)) s 
dijkstra :: Real b => H.Heap (LPath b) -> Graph a b -> LRTree b 
dijkstra h g | H.isEmpty h || isEmpty g = [] 
dijkstra h g = 
    case match v g of 
     (Just c,g') -> p:dijkstra (H.mergeAll (h':expand d p c)) g' 
     (Nothing,g') -> dijkstra h' g' 
    where (p@((v,d):_),h') = H.splitMin h 

spTree :: Real b => Node -> Graph a b -> LRTree b 
spTree v = dijkstra (H.unit [(v,0)]) 
spLength :: Real b => Node -> Node -> Graph a b -> b 
spLength s t = getDistance t . spTree s 
sp :: Real b => Node -> Node -> Graph a b -> Path 
sp s t = map fst . getLPath t . spTree s 

Reszta modules are here