0votos

Dijkstra con heap en Haskell

por josejuan hace 6 años

Tiene los tipos relajados (aristas y pesos), por lo que es polimorfo para aristas enumeradas de cualquier forma (cadenas, números, ...) y pesos de cualquier forma (entero, flotante, ...).

Implementar el algoritmo Dijkstra en grafos no dirigidos ponderados de la forma óptima (con heap).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
{-# LANGUAGE NoMonomorphismRestriction #-} 
import qualified Data.Heap as Heap 
import qualified Data.Map as Map 
import Data.Maybe (fromJust, fromMaybe, maybe) 
 
 
-- dijkstra con heap, relaja los tipos de los nodos y los pesos 
 
dijkstra :: (Eq a, Ord a, Ord b, Num b, Bounded b) => a -> Map.Map a [(a, b)] -> Map.Map a a 
dijkstra a g = solve (Heap.insert (a, 0) (Heap.empty :: Heap.MinPrioHeap a b)) (Map.insert a 0 Map.empty) Map.empty 
  where  solve q d p = if Heap.null q then p else solve q'' d' p' 
           where ((u, du), q') = fromJust $ Heap.view q 
                 (q'', d', p') = foldl chk (q', d, p) (g Map.! u) 
                 chk (_q, _d, _p) (v, w) = if dv <= du + w then (_q, _d, _p) 
                                                           else (Heap.insert (v, du + w) _q, mm (du + w) _d, mm u _p) 
                   where dv = fromMaybe maxBound $ Map.lookup v _d 
                         mm k m = Map.alter (\_ -> Just k) v m 
 
 
 
-- dada una "solución dijkstra" de un nodo, calcula la ruta más corta a otro 
 
shortestPath :: Ord a => Map.Map a a -> a -> [a] 
shortestPath p b = b : maybe [] (shortestPath p) (Map.lookup b p) 
 
 
 
 
-- transforma un grafo para acceder eficientemente a los nodos vecinos 
 
transformGraph :: (Eq a, Ord a, Num b) => [(a, a, b)] -> Map.Map a [(a, b)] 
transformGraph = foldl add Map.empty 
  where add m (u, v, p) = Map.alter (up u p) v $ Map.alter (up v p) u m 
        up u p  Nothing  = Just [(u, p)] 
        up u p (Just xs) = Just $ (u, p):xs 
 
 
 
 
gtest :: [(String, String, Int)] 
gtest = [(a, b, 1) 
        ,(a, c, 40) 
        ,(b, d, 1) 
        ,(c, d, 1) 
        ,(c, f, 2) 
        ,(d, e, 1) 
        ,(d, g, 4) 
        ,(e, h, 1) 
        ,(f, g, 1) 
        ,(g, h, 1) 
        where a = "A" 
              b = "B" 
              c = "C" 
              d = "D" 
              e = "E" 
              f = "F" 
              g = "G" 
              h = "H" 
 
test = shortestPath (dijkstra "A" $ transformGraph gtest) "F" 
 
 
-- otra versión en haskell podría ser ésta 
--    http://bonsaicode.wordpress.com/tag/dijkstra/ 
-- pero no es la versión más eficiente y además fija los tipos 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.