ハスケルでDijkstraアルゴリズムを実装する方法

Question

私の研究では、2国間の最短ルートを得る次の関数を書く必要があります。すでに2国間の接続があるかどうかを調べる関数isRouteと、2国間の接続を返す関数yieldRouteをすでに書いています。 ここでは、2国間の最短ルートを返す関数をコーディングする必要があります。

私の最初のアプローチは、両国間のすべての接続を取得し、次に最短の接続を取得することでしたが、すべての接続を取得することは、私の意見ではプログラムにとって迷惑なものです。今、私はdijstraアルゴリズムを実装するアイデアを思いつきましたが、実際にはこれもちょっと難しいと感じています。あなたは私にこのことをどうやって考えてもらえますか？ （。我々はそれらを変更することはできませんが、我々は新しいタイプを追加することが許可されているOFC）

私たちは、これらの型を使用する必要が

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) 

単に私の降伏ルート機能は、最初の検索を横幅：（SRYドイツのコメント）

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

私は今記述する必要があり、この1：

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

Dijkst RAのアルゴリズム： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

私の最初のアプローチは、このでした。（私は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 

私は基本的にHaskellでダイクストラを実装するためにいただきました！最良の方法をお知りになりたい場合、またはそれに続く別のアプローチがあります。あなたがここアルゴリズム

の大部分をコード化しているように見える

Answer 1

ですこのトピックの素晴らしい紹介です アンドリューゴールドバーグとサイモンペイトンジョーンズ：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 

をいくつかのアイデアを与えるために役立つことはHaskellでマーティンErwigによるプロジェクト休みがありmodules are here