-- CaminosMinimos.hs -- Caminos mínimos entre todos los pares de nodos de un grafo -- José A. Alonso Jiménez -- Sevilla, 22 de Enero de 2011 -- --------------------------------------------------------------------- module CaminisMinimos where -- --------------------------------------------------------------------- -- Descripción del problema -- -- --------------------------------------------------------------------- -- Cálculo de los caminos de coste mínimo entre todos los pares de nodos -- de un grafo no dirigido. -- --------------------------------------------------------------------- -- El algoritmo -- -- --------------------------------------------------------------------- -- c(i,j) es el mínimo coste del camino del vértice i al j. -- p(i,j) es el peso del arco entre i y j. Está definida por -- * Si i=j, entonces p(i,j) = 0 -- * en caso contrario, p(i,j) = infinito. -- c(i,j,k) es el mínimo coste del camino del vértice i al j, usando los -- vértices 1,...,k. -- Relación de recurrencia para calcular c(i,j): -- * c(i,j,0) = p(i,j) -- * c(i,j,k) = min {c(i,j,k-1), c(i,k,k-1)+c(k,j,k-1)} -- El algoritmo se conoce como el algoritmo de Floyd. -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Dinamica -- Nota: Elegir una implementación de los grafos. import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia -- --------------------------------------------------------------------- -- Solución mediante programación dinámica -- -- --------------------------------------------------------------------- -- Ejemplos de grafos (el 1º es el de la página 189) ej1Grafo :: Grafo Int Int ej1Grafo = creaGrafo ND (1,6) [(i,j,(v!!(i-1))!!(j-1)) | i <- [1..6], j <- [1..6]] v :: [[Int]] v = [[ 0, 4, 1, 6,100,100], [ 4, 0, 1,100, 5,100], [ 1, 1, 0,100, 8, 2], [ 6,100,100, 0,100, 2], [100, 5, 8,100, 0, 5], [100,100, 2, 2, 5, 0]] ej2Grafo :: Grafo Int Int ej2Grafo = creaGrafo ND (1,6) [(i,j,(v'!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]] v'::[[Int]] v' =[[ 0, 4,100,100,100, 2], [ 1, 0, 3, 4,100,100], [ 6, 3, 0, 7,100,100], [ 6,100,100, 0, 2,100], [100,100,100, 5, 0,100], [100,100,100, 2, 3, 0]] -- En la matriz del cálculo del camino mínimo, los índices son de la -- forma (i,j,k) y los valores de la forma (v,xs) representando que el -- camino mínimo desde el vértice i al j usando los vértices 1,...,k -- tiene un coste v y está fomado por los vértices xs. type IndiceCM = (Int,Int,Int) type ValorCM = (Int,[Int]) -- (caminosMinimos g) es la lista de los caminos mínimos entre todos los -- nodos del grafo g junto con sus costes. Por ejemplo, -- ghci> caminosMinimos ej1Grafo -- [((1,2),(2,[1,3,2])), ((1,3),(1,[1,3])), ((1,4),(5,[1,3,6,4])), -- ((1,5),(7,[1,3,2,5])),((1,6),(3,[1,3,6])),((2,3),(1,[2,3])), -- ((2,4),(5,[2,3,6,4])),((2,5),(5,[2,5])), ((2,6),(3,[2,3,6])), -- ((3,4),(4,[3,6,4])), ((3,5),(6,[3,2,5])),((3,6),(2,[3,6])), -- ((4,5),(7,[4,6,5])), ((4,6),(2,[4,6])), ((5,6),(5,[5,6]))] -- ghci> caminosMinimos ej2Grafo -- [((1,2),(4,[1,2])), ((1,3),(7,[1,2,3])),((1,4),(4,[1,6,4])), -- ((1,5),(5,[1,6,5])),((1,6),(2,[1,6])), ((2,3),(3,[2,3])), -- ((2,4),(4,[2,4])), ((2,5),(6,[2,4,5])),((2,6),(3,[2,1,6])), -- ((3,4),(7,[3,4])), ((3,5),(9,[3,4,5])),((3,6),(6,[3,2,1,6])), -- ((4,5),(2,[4,5])), ((4,6),(8,[4,1,6])),((5,6),(13,[5,4,1,6]))] caminosMinimos :: (Grafo Int Int) -> [((Int,Int), ValorCM)] caminosMinimos g = [((i,j), valor t (i,j,n)) | i <- [1..n], j <- [i+1..n]] where n = length (nodos g) t = dinamica (calculaCM g) (cotasCM n) -- (calculaCM g t (i,j,k)) es el valor del camino mínimo desde el vértice -- i al j usando los vértices 1,...,k del grafo g y la tabla t de los -- valores anteriores al índice (i,j,k). calculaCM :: (Grafo Int Int) -> Tabla IndiceCM ValorCM -> IndiceCM -> ValorCM calculaCM g t (i,j,k) | k==0 = (peso i j g , if i==j then [i] else [i,j]) | v1<=v2 = (v1,p) | otherwise = (v2,p1++p2) where (v1,p) = valor t (i,j,k-1) (a,p1) = valor t (i,k,k-1) (b,_:p2) = valor t (k,j,k-1) v2 = a+b -- (cotasCM n) son las cotasCM de la matriz para resolver el problema de los -- caminos mínimos en un grafo con n nodos. cotasCM :: Int -> ((Int,Int,Int),(Int,Int,Int)) cotasCM n = ((1,1,0),(n,n,n)) -- Se puede observar el cálculo de la solución como sigue: {- ghci> dinamica (calculaCM ej1Grafo) (cotasCM 6) Tbl [ ((1,1,0),(0,[1])), ((1,1,1),(0,[1])), ((1,1,2),(0,[1])), ((1,1,3),(0,[1])), ((1,1,4),(0,[1])), ((1,1,5),(0,[1])), ((1,1,6),(0,[1])), ((1,2,0),(4,[1,2])), ((1,2,1),(4,[1,2])), ((1,2,2),(4,[1,2])), ((1,2,3),(2,[1,3,2])), ((1,2,4),(2,[1,3,2])), ((1,2,5),(2,[1,3,2])), ((1,2,6),(2,[1,3,2])), ((1,3,0),(1,[1,3])), ((1,3,1),(1,[1,3])), ((1,3,2),(1,[1,3])), ((1,3,3),(1,[1,3])), ((1,3,4),(1,[1,3])), ((1,3,5),(1,[1,3])), ((1,3,6),(1,[1,3])), ((1,4,0),(6,[1,4])), ((1,4,1),(6,[1,4])), ((1,4,2),(6,[1,4])), ((1,4,3),(6,[1,4])), ((1,4,4),(6,[1,4])), ((1,4,5),(6,[1,4])), ((1,4,6),(5,[1,3,6,4])), ((1,5,0),(100,[1,5])), ((1,5,1),(100,[1,5])), ((1,5,2),(9,[1,2,5])), ((1,5,3),(7,[1,3,2,5])),((1,5,4),(7,[1,3,2,5])), ((1,5,5),(7,[1,3,2,5])), ((1,5,6),(7,[1,3,2,5])),((1,6,0),(100,[1,6])), ((1,6,1),(100,[1,6])), ((1,6,2),(100,[1,6])), ((1,6,3),(3,[1,3,6])), ((1,6,4),(3,[1,3,6])), ((1,6,5),(3,[1,3,6])), ((1,6,6),(3,[1,3,6])), ((2,1,0),(4,[2,1])), ((2,1,1),(4,[2,1])), ((2,1,2),(4,[2,1])), ((2,1,3),(2,[2,3,1])), ((2,1,4),(2,[2,3,1])), ((2,1,5),(2,[2,3,1])), ((2,1,6),(2,[2,3,1])), ((2,2,0),(0,[2])), ((2,2,1),(0,[2])), ((2,2,2),(0,[2])), ((2,2,3),(0,[2])), ((2,2,4),(0,[2])), ((2,2,5),(0,[2])), ((2,2,6),(0,[2])), ((2,3,0),(1,[2,3])), ((2,3,1),(1,[2,3])), ((2,3,2),(1,[2,3])), ((2,3,3),(1,[2,3])), ((2,3,4),(1,[2,3])), ((2,3,5),(1,[2,3])), ((2,3,6),(1,[2,3])), ((2,4,0),(100,[2,4])), ((2,4,1),(10,[2,1,4])), ((2,4,2),(10,[2,1,4])), ((2,4,3),(8,[2,3,1,4])), ((2,4,4),(8,[2,3,1,4])),((2,4,5),(8,[2,3,1,4])), ((2,4,6),(5,[2,3,6,4])), ((2,5,0),(5,[2,5])), ((2,5,1),(5,[2,5])), ((2,5,2),(5,[2,5])), ((2,5,3),(5,[2,5])), ((2,5,4),(5,[2,5])), ((2,5,5),(5,[2,5])), ((2,5,6),(5,[2,5])), ((2,6,0),(100,[2,6])), ((2,6,1),(100,[2,6])), ((2,6,2),(100,[2,6])), ((2,6,3),(3,[2,3,6])), ((2,6,4),(3,[2,3,6])), ((2,6,5),(3,[2,3,6])), ((2,6,6),(3,[2,3,6])), ((3,1,0),(1,[3,1])), ((3,1,1),(1,[3,1])), ((3,1,2),(1,[3,1])), ((3,1,3),(1,[3,1])), ((3,1,4),(1,[3,1])), ((3,1,5),(1,[3,1])), ((3,1,6),(1,[3,1])), ((3,2,0),(1,[3,2])), ((3,2,1),(1,[3,2])), ((3,2,2),(1,[3,2])), ((3,2,3),(1,[3,2])), ((3,2,4),(1,[3,2])), ((3,2,5),(1,[3,2])), ((3,2,6),(1,[3,2])), ((3,3,0),(0,[3])), ((3,3,1),(0,[3])), ((3,3,2),(0,[3])), ((3,3,3),(0,[3])), ((3,3,4),(0,[3])), ((3,3,5),(0,[3])), ((3,3,6),(0,[3])), ((3,4,0),(100,[3,4])), ((3,4,1),(7,[3,1,4])), ((3,4,2),(7,[3,1,4])), ((3,4,3),(7,[3,1,4])), ((3,4,4),(7,[3,1,4])), ((3,4,5),(7,[3,1,4])), ((3,4,6),(4,[3,6,4])), ((3,5,0),(8,[3,5])), ((3,5,1),(8,[3,5])), ((3,5,2),(6,[3,2,5])), ((3,5,3),(6,[3,2,5])), ((3,5,4),(6,[3,2,5])), ((3,5,5),(6,[3,2,5])), ((3,5,6),(6,[3,2,5])), ((3,6,0),(2,[3,6])), ((3,6,1),(2,[3,6])), ((3,6,2),(2,[3,6])), ((3,6,3),(2,[3,6])), ((3,6,4),(2,[3,6])), ((3,6,5),(2,[3,6])), ((3,6,6),(2,[3,6])), ((4,1,0),(6,[4,1])), ((4,1,1),(6,[4,1])), ((4,1,2),(6,[4,1])), ((4,1,3),(6,[4,1])), ((4,1,4),(6,[4,1])), ((4,1,5),(6,[4,1])), ((4,1,6),(5,[4,6,3,1])), ((4,2,0),(100,[4,2])), ((4,2,1),(10,[4,1,2])), ((4,2,2),(10,[4,1,2])), ((4,2,3),(8,[4,1,3,2])),((4,2,4),(8,[4,1,3,2])), ((4,2,5),(8,[4,1,3,2])), ((4,2,6),(5,[4,6,3,2])),((4,3,0),(100,[4,3])), ((4,3,1),(7,[4,1,3])), ((4,3,2),(7,[4,1,3])), ((4,3,3),(7,[4,1,3])), ((4,3,4),(7,[4,1,3])), ((4,3,5),(7,[4,1,3])), ((4,3,6),(4,[4,6,3])), ((4,4,0),(0,[4])), ((4,4,1),(0,[4])), ((4,4,2),(0,[4])), ((4,4,3),(0,[4])), ((4,4,4),(0,[4])), ((4,4,5),(0,[4])), ((4,4,6),(0,[4])), ((4,5,0),(100,[4,5])), ((4,5,1),(100,[4,5])), ((4,5,2),(15,[4,1,2,5])),((4,5,3),(13,[4,1,3,2,5])),((4,5,4),(13,[4,1,3,2,5])), ((4,5,5),(13,[4,1,3,2,5])),((4,5,6),(7,[4,6,5])),((4,6,0),(2,[4,6])), ((4,6,1),(2,[4,6])), ((4,6,2),(2,[4,6])), ((4,6,3),(2,[4,6])), ((4,6,4),(2,[4,6])), ((4,6,5),(2,[4,6])), ((4,6,6),(2,[4,6])), ((5,1,0),(100,[5,1])), ((5,1,1),(100,[5,1])), ((5,1,2),(9,[5,2,1])), ((5,1,3),(7,[5,2,3,1])), ((5,1,4),(7,[5,2,3,1])),((5,1,5),(7,[5,2,3,1])), ((5,1,6),(7,[5,2,3,1])), ((5,2,0),(5,[5,2])), ((5,2,1),(5,[5,2])), ((5,2,2),(5,[5,2])), ((5,2,3),(5,[5,2])), ((5,2,4),(5,[5,2])), ((5,2,5),(5,[5,2])), ((5,2,6),(5,[5,2])), ((5,3,0),(8,[5,3])), ((5,3,1),(8,[5,3])), ((5,3,2),(6,[5,2,3])), ((5,3,3),(6,[5,2,3])), ((5,3,4),(6,[5,2,3])), ((5,3,5),(6,[5,2,3])), ((5,3,6),(6,[5,2,3])), ((5,4,0),(100,[5,4])), ((5,4,1),(100,[5,4])), ((5,4,2),(15,[5,2,1,4])), ((5,4,3),(13,[5,2,3,1,4])),((5,4,4),(13,[5,2,3,1,4])),((5,4,5),(13,[5,2,3,1,4])), ((5,4,6),(7,[5,6,4])), ((5,5,0),(0,[5])), ((5,5,1),(0,[5])), ((5,5,2),(0,[5])), ((5,5,3),(0,[5])), ((5,5,4),(0,[5])), ((5,5,5),(0,[5])), ((5,5,6),(0,[5])), ((5,6,0),(5,[5,6])), ((5,6,1),(5,[5,6])), ((5,6,2),(5,[5,6])), ((5,6,3),(5,[5,6])), ((5,6,4),(5,[5,6])), ((5,6,5),(5,[5,6])), ((5,6,6),(5,[5,6])), ((6,1,0),(100,[6,1])), ((6,1,1),(100,[6,1])), ((6,1,2),(100,[6,1])), ((6,1,3),(3,[6,3,1])), ((6,1,4),(3,[6,3,1])), ((6,1,5),(3,[6,3,1])), ((6,1,6),(3,[6,3,1])), ((6,2,0),(100,[6,2])), ((6,2,1),(100,[6,2])), ((6,2,2),(100,[6,2])), ((6,2,3),(3,[6,3,2])), ((6,2,4),(3,[6,3,2])), ((6,2,5),(3,[6,3,2])), ((6,2,6),(3,[6,3,2])), ((6,3,0),(2,[6,3])), ((6,3,1),(2,[6,3])), ((6,3,2),(2,[6,3])), ((6,3,3),(2,[6,3])), ((6,3,4),(2,[6,3])), ((6,3,5),(2,[6,3])), ((6,3,6),(2,[6,3])), ((6,4,0),(2,[6,4])), ((6,4,1),(2,[6,4])), ((6,4,2),(2,[6,4])), ((6,4,3),(2,[6,4])), ((6,4,4),(2,[6,4])), ((6,4,5),(2,[6,4])), ((6,4,6),(2,[6,4])), ((6,5,0),(5,[6,5])), ((6,5,1),(5,[6,5])), ((6,5,2),(5,[6,5])), ((6,5,3),(5,[6,5])), ((6,5,4),(5,[6,5])), ((6,5,5),(5,[6,5])), ((6,5,6),(5,[6,5])), ((6,6,0),(0,[6])), ((6,6,1),(0,[6])), ((6,6,2),(0,[6])), ((6,6,3),(0,[6])), ((6,6,4),(0,[6])), ((6,6,5),(0,[6])), ((6,6,6),(0,[6]))] -}