When I try to code the shortest path algorithm, I come across something strange. After the floydWarshall function generates an adjacency matrix in the form of an array, the main function tries to query the array several times (in the replicateM_ loop).
I found that my code is terribly slow. So I put traceShow "doing" at the top of floydWarshall and rerun to find that everyone res ! (start,end) res ! (start,end) calls floydWarshall several times.
Why is the array re-generated every time?
Full source code with sample input: https://gist.github.com/cwyang/27ab81bee731e6d01bb3a7483fdb748e
floydWarshall :: AdjMatrix (Maybe Int) -> AdjMatrix (Maybe Int) floydWarshall am = traceShow "doing" $ runST $ do arr <- thaw am :: ST s (STArray s (Vertex,Vertex) (Maybe Int)) sequence_ [ go arr kij | k <- r, i <- r, j <- r] freeze arr where ((minb,_), (maxb,_)) = bounds am r = [minb..maxb] go :: STArray s (Vertex,Vertex) (Maybe Int) -> Vertex -> Vertex -> Vertex -> ST s () go arr kij = do ij <- readArray arr (i,j) ik <- readArray arr (i,k) kj <- readArray arr (k,j) case (ik, kj) of (Nothing, _) -> return () (_, Nothing) -> return () (Just a, Just b) -> case ij of Nothing -> do writeArray arr (i,j) $ Just (a+b) (Just c) -> when (c > a+b) $ do writeArray arr (i,j) $ Just (a+b) readInt :: B.ByteString -> Int readInt = fst . fromJust . B.readInt main :: IO () main = do [n,m] <- rl edges <- replicateM m $ do [from,to,weight] <- rl return (from,to,weight) [q] <- rl let am = buildAdjMatrix (1,n) edges res= floydWarshall am replicateM_ q $ do [start,end] <- rl putStrLn . show $ maybe (-1) id (res ! (start,end)) where rl = map readInt . B.words <$> B.getLine
Run Example:
$ graph < floyd3.txt hs "doing" <-- floydWarshall keeps calling 1395 "doing" 975 "doing" 1593 "doing" 1023 "doing" 1521 ...