## Shortest Path Problem ![graph.png](https://www.fpcomplete.com/media/5217b2d7-bb7c-4364-a280-6ea2c5775b8b.png) _In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized._ Reference [Shortest Path Problem (wiki)](http://en.wikipedia.org/wiki/Shortest_path_problem) ## Floyd-Warshall Algorithm The Floyd-Warshall algorithm compares all possible paths through the graph between each pair of vertices. Algorithm has a nice recursive definition for calculating the shortest path between two vertices: [Floyd-Warshall](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm). To find a path from `i` to `j` the algorithm will test between the direct path `{[i,..,j]}` using vertices `{1..k}` as intermediate points along the way and using a step `k+1`: `{[i,..,k+1],[k+1,..,j]}`. Recursive base case `k=0` is the edge `[i,j]`. Normally in applications, the shortest path reconstruction is also required. In wiki page there is a slight modification in the algorithm: When a new shortest path is found, the matrix containing the paths is updated. This method won't fit directly in the functional programming paradigm. I had some problems to design path reconstruction function and I ended up with a solutions which calls `shortest` function recursively and I found this solution quite hard to read. Anyway, it solves the desired problem and could be improved using memoization. ## Solution ``` active haskell {-# START_FILE Floyd.hs #-} module Floyd (floyd_warshall) where floyd_warshall start end graph = (dist, [start] ++ route ++ [end]) where dist = shortest (start, end, length graph) graph route = path (start, end, length graph) graph -- Calculates the value of shortest route shortest (i,j,0) g = g !! (i-1) !! (j-1) -- Transition value from graph shortest (i,j,k) g = min (shortest (i,j,k-1) g) $ (shortest (i,k,k-1) g) + (shortest (k,j,k-1) g) -- Reconstructs the shortest path path (i,j,0) _ = [] path (i,j,k) g | direct < step = path(i,j,k-1) g | otherwise = (path(i,k,k-1) g) ++ [k] ++ (path(k,j,k-1) g) where direct = shortest (i,j,k-1) g step = (shortest (i,k,k-1) g) + (shortest (k,j,k-1) g) {-# START_FILE Main.hs #-} import Data.List (transpose) import Floyd main = do -- show Example problem contents <- readFile "graph.txt" let graph = readGraph contents output $ floyd_warshall 1 8 graph -- /show output x = do putStrLn $ "(Length, [nodes])" putStrLn $ show x readGraph = transpose . str2int . map words . lines str2int = map.map $ zero2inf . fromIntegral . (\xs -> read xs :: Int) zero2inf x = if x == 0 then 1/0 else x {-# START_FILE graph.txt #-} 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 15 13 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 6 13 0 0 0 0 0 0 0 0 7 0 9 0 0 0 5 0 0 0 0 0 0 0 0 0 0 4 18 0 ``` ## Memoization Solution above will actually use much more computation and memory than is needed. It's the first working version and I hope I'll have time to improve it. The first improvement for this algorithm would be implementing memoization. This technique allows to use already calculated values. ## Complexity The algorithm requires three iterations through vertices (paths between each i and j and steps 1..k), thus `O(V^3)`.