하스켈에서 Dijkstra 알고리즘을 구현하는 방법

Question

제 연구를 위해 저는 두 국가 간의 최단 경로를 얻는 다음 함수를 작성해야합니다. 이미 두 나라 간의 연결이 있는지를 확인하는 isRoute 함수와 두 나라 간의 연결을 반환하는 yieldRoute 함수를 이미 작성했습니다. 이제 두 나라 간의 최단 경로를 반환하는 함수를 작성해야합니다.

내 첫 번째 접근 방식은 양국 간의 모든 연결을 얻은 다음 가장 짧은 연결을 얻는 것이었지만, 모든 연결을 얻는 것은 제 생각에는 프로그래머에게는 성가신 일입니다. 이제 dijstra 알고리즘을 구현하는 아이디어를 생각해 냈습니다. 그러나 실제로는 너무 어렵습니다. 너희들이 나에게이 일을하는 법을 줄 수 있니? 우리는 이러한 유형을 사용할 필요가

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) 

은 내 수율 경로 기능은 단순히 첫 번째 검색을 폭 (우리가 그들을 변경할 수 있지만, 우리는 새로운 유형을 추가 할 수 있습니다 OFC되지 않습니다.) : (SRY

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

Dijkst을 :

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

이 하나) 독일어 의견을 내가 지금 작성해야 라 알고리즘 : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

내 첫 번째 방법이 있었다 : 나는 기본적으로 가장 좋은 방법은 하스켈에서 익스트라을 구현하기 위해 무슨 알고 싶어

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 

경우, 또는 (I 내가 getallRoutes 문제가 있었다 말했듯이) 내가 따를 수있는 또 다른 접근법이있다.

Answer 1

당신에게 제공하는 데 도움이 될 수 있습니다 하스켈 마틴 Erwig에 의해 프로젝트입니다 것 같다 이 주제에 대해 훌륭하고 훌륭한 소개입니다. Andrew Goldberg 및 Simon Peyton Jones : http://www.ukuug.org/events/agm2010/ShortestPath.pdf

코드를 작성하기 전에 문제를 이해하는 데 도움이되었습니다. 그것은 Dijkstra의 알고리즘을 잘 설명하며, 구현하기 쉽습니다. 또한 원래 알고리즘에 대한 모든 종류의 개선점을 제공합니다.이 알고리즘은 나에게 영감을 주었던 것만 큼 영감을줍니다.

Answer 2

당신은 알고리즘 여기

의 큰 부분을 코딩 몇 가지 아이디어

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

가 나머지 modules are here