Dijkstra's shortest path algorithm

>  module Dijkstra(Weight, dijkstra, prim)

>  where

>  import Prelude hiding (lookup)

>  import Graph

>  import Unbalanced

>  decrease                      :: (Ord k, Ord p) => (Binding k p) -> PSQ k p -> PSQ k p

>  decrease (k :-> p) q          =  adjust (min p) k q

> 

>  decreaseList                  :: (Ord k, Ord p) => [Binding k p] -> PSQ k p -> PSQ k p

>  decreaseList bs q             =  foldr decrease q bs

Dijkstra's shortest path algorithm.

>  type Weight                   =  Vertex -> Vertex -> Double

> 

>  dijkstra                      :: Graph -> Weight -> Vertex -> [Binding Vertex Double]

>  dijkstra g w s                =  loop (decrease (s :-> 0) q0)

>    where

>    q0                          =  fromOrdList [ v :-> maxBound | v <- vertices g ]

> 

>    loop q'                     =  case minView q' of

>      Empty                     -> []

>      Min (u :-> d) q           -> (u :-> d) : loop (decreaseList bs q)

>        where bs                =  [ v :-> d + w u v | v <- adjacent g u ]

Prim's algorithm for computing a minimum spanning tree.

>  prim                         :: Graph -> Weight -> Vertex -> [Binding Vertex Double]

>  prim g w s                    =  loop (decrease (s :-> 0) q0)

>    where

>    q0                          =  fromOrdList [ v :-> maxBound | v <- vertices g ]

> 

>    loop q'                     =  case minView q' of

>      Empty                     -> []

>      Min (u :-> d) q           -> (u :-> d) : loop (decreaseList bs q)

>        where bs                =  [ v :-> w u v | v <- adjacent g u ]

Note that Prim's algorithm differs from Dijkstra's algorithm only in the last line.

We make Double an instance of Bounded so that we can use maxBound for the initialization in Dijkstra's and in Prim's algorithm.

>  instance Bounded Double where

>    minBound                    =  - 1.0e40

>    maxBound                    =    1.0e40