## 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)`.