Algoritmo de Prim


Este algoritmo es un metodo sistematico para deteminar el árbol mínimo de expación en un grafo conexo.

Descripción

Algoritmo de Prim


Metodo sistematico, Si, es un patron con una serie de pasos ordenados y definidos


Árbol de expansion minimo, esto refiere al árbol de máximo alcance cuyo valor es minimo, es decir, la suma de sus aristas es minima.


Grafo conectado, el grafo debe ser conexo y no debe tener ciclos.


Aclaración

Árbol de expansión, árbol generador y árbol recubridor son terminos equivalentes.

Funcionamiento

Algoritmo de Prim


Objetivo: Encontrar el árbol recubridor mínimo.


El algorimo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima.


Cuando no quedan vertices por agregar, esta completo el árbol recubridor minimo.


Requisitos:


Algoritmo de prim

Ejercicio gráfico


Fig.1

  • Se marca un nodo cualquiera, este será el nodo de partida.

  • Seleccionamos la arista de menor valor incidente en el nodo de partida, y marcamos el otro nodo en el que índice.

  • Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

  • El proceso termina cuando tenemos todos los nodos del grafo marcados
  • Algoritmo de prim

    Programando el Algoritmo


          #!/usr/bin/env python
          # -*- coding: utf-8 -*-
          from collections import defaultdict
          from heapq import *
    
          def prim(grafo):
              #crea listas en base a un indice comun, en este caso los indices seran los nodos 1 y 2
              #en cada indice se almacena la tupla (c, n1, n2)
              conn = defaultdict( list )
              for c,n1,n2 in grafo['aristas']:
                  #direccionamiento
                  conn[ n1 ].append( (c, n1, n2) )
                  conn[ n2 ].append( (c, n2, n1) )
    
              recorrido = []
    
              #toma el nodo inicial
              usado = set( grafo['nodos'][0] )
              #toma las aristas que contienen el nodo inicial
              nueva_arista = conn[ grafo['nodos'][0] ][:]
    
              #mantiene en la posicion 0 el menor valor de la lista
              heapify( nueva_arista )
          

    Algoritmo de prim

    Programando el Algoritmo


    
        while nueva_arista:
            #saca el primer valor de la lista y lo almacena en costo, n1, n2
            costo, n1, n2 = heappop( nueva_arista )
            #pregunta si el nodo final de la arista no ha sido visitado
            if n2 not in usado:
                usado.add( n2 )
                #agrega la arista al recorrido
                recorrido.append( ( costo, n1, n2  ) )
                #print "recorrido",recorrido
    
                #recorre la lista de nodos invertidos y en caso de que no se aya
                #pasado por el nodo lo agrega a la lista de aristas.
                for e in conn[ n2 ]:
                    # e[2] corresponde al "nodo de llegada"
                    if e[ 2 ] not in usado:
                        #agrega "e" a nueva_arista
                        heappush( nueva_arista, e )
        return recorrido
          

    Algoritmo de prim

    Grafo a evaluar


    Fig.2


    Para probar el algoritmo usaremos el grafo de la Fig.2


    Para logarlo utilizaremos una estructura de datos que represente los nodos y los costos de las aristas.

    Algoritmo de prim

    Programando el Algoritmo


    
            #diccionario
            grafo = {
                    'nodos': ['A','B','C','D','E','F','G'],
                    'aristas': [
                        (7,'A','B'),(5,'A','D'),
                        (8,'B','C'),(9,'B','D'), (7,'B','E'),
                        (5,'C','E'),
                        (15,'D','E'),(6,'D','F'),
                        (8,'E','F'),(9,'E','G'),
                        (11,'F','G')
                        ]
                    }
    
            print "prim:", prim(grafo)
          

    Algoritmo de Bellman-Ford


    Es un algorimo que encuenra el camino mas corto desde un vertice puntual hasta los demas vertices en un grafo ponderado.

    Algoritmo de Bellman-Ford

    Descripción


    Genera el camino más corto en un Grafo dirigido ponderado .


    Se parte de un nodo fuente hacia los demás nodos.


    La especial de este algoritmo con respecto a los demás es que los pesos pueden tener valores negativos ya que permite detectar la existencia de un ciclo negativo .

    Funcionamiento

    Algoritmo de Bellmab-Ford


    Objetivo: Encontrar el camino minimo desde un vertice hacia todos los demas.


    El algoritmo parte de un vértice origen que será ingresado, luego se selecíonan los vértices de menor peso y se actualizan sus distancias mediante el paso de relajación , Bellman-Ford simplemente relaja todas las aristas y lo hace |V| – 1 veces, siendo |V| el número de vértices del grafo


    Requisitos:


    Relajación


    
          void relajacion( int actual , int adyacente , int peso ){
    
            //Si la distancia del origen al vertice actual + peso de su arista
            //es menor a la distancia del origen al vertice adyacente
    
              if( distancia[ actual ] + peso < distancia[ adyacente ] ){
    
              //relajamos el vertice actualizando la distancia
    
              distancia[ adyacente ] = distancia[ actual ] + peso;
              previo[ adyacente ] = actual;
              }
          }
    
          

    Algoritmo de Bellman-Ford

    Ejemplo gráfico y Pseudo código

    Algoritmo de Bell-Ford

    Grafo a evaluar


    Fig.3


    Para probar el algoritmo usaremos el grafo dirijido de la Fig.3


    Para logarlo utilizaremos una modulo escrito C++ rendereado a node.js.


    Node nos facilitara la creación de la estructura de datos del grafo.

    Algoritmo de Bellman-Ford

    Implementando el algoritmo


            // Usamos los modulos
            var bellman_ford = require('bellman-ford');
            var graph = new bellman_ford();
    
            // Creamos los nodos y definimos las relaciones y los costos
            graph.add_node("S");
            graph.add_node("A");
            graph.add_node("C");
            graph.add_node("B");
            graph.add_node("T");
    
            graph.add_edge("S", "B", 6);
            graph.add_edge("S", "A", 7);
            graph.add_edge("A", "C", -3);
            graph.add_edge("A", "T", 9);
            graph.add_edge("T", "C", 7);
            graph.add_edge("T", "S", 2);
            graph.add_edge("C", "B", -2);
            graph.add_edge("B", "C", 5);
            graph.add_edge("B", "T", -4);
            graph.add_edge("B", "A", 8);
    
            // Mostramos el resultado y fijamos el vertice fuente
            console.log(graph.bellmanford("S"));
    
          

    ¿ Para que me sirve todo eso ?


    Los algoritmos expuestos pueden ser utilizados en muchos campos, estos son de gran importancia en la computación.


    Algunos casos de uso:


    • Redes(servidores, energia, transporte)
    • Inteligencia artificial, redes neuronales
    • Electronica, circuitos
    • Internet, Protocolos
    • Investigación de operaciones

    Preguntas ?


    Descarga de material

    <Gracias!>

    Mail julioc255io@gmail.com

    Proyectos