Wie man den Dijkstra-Algorithmus in Haskell implementiert

Question

Für meine Studien muss ich die folgende Funktion schreiben, die die kürzeste Route zwischen zwei Ländern bekommt. Ich habe bereits eine Funktion isRoute geschrieben, die prüft, ob es eine Verbindung zwischen zwei Ländern gibt, und eine Funktion yieldRoute, die nur eine Verbindung zwischen zwei Ländern zurückgibt. Jetzt muss ich eine Funktion codieren, die die kürzeste Route zwischen zwei Ländern zurückgibt.

Meine erste Annäherung war, alle Verbindungen zwischen den zwei Ländern zu bekommen und dann die kürzeste zu bekommen, aber alle Verbindungen zu bekommen ist irgendwie nervig zu programmieren meiner Meinung nach. Jetzt komme ich auf die Idee, einen Dijstra-Algorithmus zu implementieren, aber ich finde das auch irgendwie schwer. Kannst du mir eine Idee geben, wie das geht?

Wir diese Art verwenden, haben

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) 

Funktion Meine Ausbeute Route, die einfach Breitensuche ist (wir werden sie nicht mehr ändern, aber OFC wir neue Typen hinzufügen dürfen.): (Sry für Deutsch Kommentare)

-- 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 

Dieses habe ich jetzt schreiben:

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

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

Mein erster Ansatz war: (wie gesagt, ich Probleme mit der getallRoutes hatte)

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 

Ich mag im Grunde wissen, was ist der beste Weg, Dijkstra in Haskell zu implementieren, oder wenn Es gibt noch einen anderen Ansatz, dem ich folgen könnte.

Answer 1

Es kann helfen ist eine wunderbare und brillante Einführung in dieses Thema von Andrew Goldberg und Simon Peyton Jones: http://www.ukuug.org/events/agm2010/ShortestPath.pdf

Es hat mir geholfen, das Problem zu verstehen, bevor überhaupt Code geschrieben wurde. Es erklärt Dijkstras Algorithmus sehr gut, nach dem Sie es leicht zu implementieren finden. Es gibt auch alle möglichen Verbesserungen des ursprünglichen Algorithmus, die Sie wahrscheinlich genauso inspirieren werden wie mich.

Answer 2

Sie scheinen großen Teil des Algorithmus zu haben kodiert

Hier ist ein Projekt von Martin Erwig in Haskell, die Sie geben einige Ideen

-- 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 

Der Rest modules are here