Я новичок в Хаскеле. Я скомпилировал код, и открывается основная оболочка. Я не знаю, как ввести края графика и получить результат. Любая помощь будет оценена по достоинству.
Имея граф и исходную вершину src в графе, найти кратчайшие пути от src ко всем вершинам данного графа. Граф может содержать ребра с отрицательным весом.
{-# LANGUAGE BangPatterns #-}
module Main where
import Control.DeepSeq
import Data.Functor
import Data.Int
import Data.Vector.Unboxed ((//))
import qualified Data.Vector.Unboxed as V
--import Debug.Trace
type Vertex = Int
type Dist = Int32
type Edge = (Vertex, Vertex, Dist)
type EdgeVec = V.Vector Edge
type CostVec = V.Vector Dist
readEdge :: String -> Edge
readEdge s = let [v1, v2, w] = words s
in (read v1, read v2, read w)
bfStep :: EdgeVec -> CostVec -> CostVec
bfStep edges !prev = V.unsafeAccumulate min prev $ V.map mincost edges
where
mincost :: Edge -> (Int, Int32)
mincost (s, h, c) = (h, cost s c)
cost w c = let precost = prev `V.unsafeIndex` w
in if precost == maxBound then maxBound else precost + c
mkEdgeVec :: Int -> [String] -> EdgeVec
mkEdgeVec nvert inp = V.unfoldr step (nvert, inp)
where
step (n, s:xs) = Just (readEdge s, (n, xs))
step (0, []) = Nothing
step (!n, []) = Just ((0, n, 0), (n - 1, []))
main :: IO()
main = do
header:body <- lines <$> getContents
let nvert = read $ head $ words header
let edgelist = mkEdgeVec nvert body
let bfbase = V.replicate (nvert + 1) maxBound // [(0, 0)]
print $ edgelist `deepseq` "running"
let bfout = iterate (bfStep edgelist) bfbase !! nvert
let bfcheck = bfStep edgelist bfout
let hasCycle = V.any id $ V.zipWith (/=) bfout bfcheck
putStrLn $ if hasCycle then "Cycle" else show $ V.minimum bfout
input.txt
в том же каталоге, что и программа, запустить консоль и запустить вашу программу (если исполняемый файл называетсяbellmanford
) какbellmanford < input.txt
. (В Linux вы должны запустить программу в текущем каталоге как./bellmanford
.) - person Davislor   schedule 28.05.2017