私の研究では、2つの国の間の最短ルートを取得する次の関数を作成する必要があります。2つの国の間に接続があるかどうかをチェックする関数isRouteと、2つの国の間に接続を返すだけの関数yieldRouteを既に作成しました。次に、2つの国間の最短ルートを返す関数をコーディングする必要があります。
私の最初のアプローチは、2つの国の間のすべての接続を取得してから、最短のものを取得することでしたが、すべての接続を取得することは、私の意見ではプログラムに少し迷惑です。今、私は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)
幅優先探索である私の降伏ルート関数:(ドイツ語のコメントを求めて）
-- 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
これは私が今書かなければならないものです：
yieldFastestRoute :: Connections -> Country -> Country -> Itinerary
ダイクストラアルゴリズム： 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でダイクストラを実装するための最良の方法を知りたいです。または私が従うことができる別のアプローチがあるかどうかを知りたいです。