AMIGOS PARA SIEMPRE: Matemáticas

Algoritmos de grafos

algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford) genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristaspuede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad matemática; […] surgen de una forma natural en la reducción a problemas de caminos más cortos”, y son un ejemplo de una reducción del problema del camino hamiltoniano que es NP-completo hasta el problema de caminos más cortos con pesos generales. Si un grafo contiene un ciclo de coste total negativo entonces este grafo no tiene solución. El algoritmo es capaz de detectar este caso.

Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará el camino más corto que no repite ningún vértice. La complejidad de este problema es al menos la del problema del camino más largo de complejidad NP-Completo.

Algoritmo

El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Las repeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez. A diferencia de la solución voraz, la cual depende de la suposición de que los pesos sean positivos, esta solución se aproxima más al caso general.

Existen dos versiones:

Versión no optimizada para grafos con ciclos negativos, cuyo coste de tiempo es O(VE).
Versión optimizada para grafos con aristas de peso negativo, pero en el grafo no existen ciclos de coste negativo, cuyo coste de tiempo, es también O(VE).

   bool BellmanFord(Grafo G, nodo_origen s)
      // inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que 
      // tiene distancia 0
       for v ∈ V[G] do
           distancia[v]=INFINITO
           predecesor[v]=NIL
       distancia[s]=0
       // relajamos cada arista del grafo tantas veces como número de nodos -1 haya en el grafo
       for i=1 to |V[G]|-1 do
           for (u, v) ∈ E[G] do
               if distancia[v]>distancia[u] + peso(u, v) then
                   distancia[v] = distancia[u] + peso (u, v)
                   predecesor[v] = u
       // comprobamos si hay ciclos negativo
       for (u, v) ∈ E[G] do
           if distancia[v] > distancia[u] + peso(u, v) then
               print ("Hay ciclo negativo")
               return FALSE
       return TRUE

  bool BellmanFord_Optimizado(Grafo G, nodo_origen s)
       // inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que
       // tiene distancia 0. Para ello lo hacemos recorriéndonos todos los vértices del grafo
       for v ∈ V[G] do
           distancia[v]=INFINITO
           padre[v]=NIL
       distancia[s]=0
       encolar(s, Q)
       en_cola[s]=TRUE
       while Q!=0 then
           u = extraer(Q)
           en_cola[u]=FALSE
           // relajamos las aristas
           for v ∈ ady[u] do
               if distancia[v]>distancia[u] + peso(u, v) then
                   distancia[v] = distancia[u] + peso (u, v)
                   padre[v] = u
                   if en_cola[v]==FALSE then
                       encolar(v, Q)
                       en_cola[v]=TRUE

Aplicaciones de encaminamiento

Una variante distribuida del Algoritmo del Bellman-Ford se usa en protocolos de encaminamiento basados en vector de distancias, por ejemplo el Protocolo de encaminamiento de información (RIP). El algoritmo es distribuido porque envuelve una serie de nodos (routers) dentro de un Sistema autónomo(AS), un conjunto de redes y dispositivos router IP administrados típica-mente por un Proveedor de Servicio de Internet (ISP). Se compone de los siguientes pasos:

Cada nodo calcula la distancia entre él mismo y todos los demás dentro de un AS y almacena esta información en una tabla.
Cada nodo envía su tabla a todos los nodos vecinos.
Cuando un nodo recibe las tablas de distancias de sus vecinos, éste calcula la ruta más corta a los demás nodos y actualiza su tabla para reflejar los cambios.

Las desventajas principales del algoritmo de Bellman-Ford en este ajuste son:

No escala bien
Los cambios en la topología de red no se reflejan rápidamente ya que las actualizaciones se distribuyen nodo por nodo.
Contando hasta el infinito(si un fallo de enlace o nodo hace que un nodo sea inalcanzable desde un conjunto de otros nodos, éstos pueden estar siempre aumentando gradualmente sus cálculos de distancia a él, y mientras tanto puede haber bucles de enrutamiento)

Mejoras

En 1970 Yen describió una mejora del algoritmo Bellman-Ford para un grafo sin ciclos con peso negativo. Esta mejora primero asigna un orden arbitrario lineal a todos los vértices y luego divide el conjunto de todas las aristas en uno o dos subconjuntos. El primer subconjunto, E_f, contiene todas las aristas (v_i,v_j) tales que i < j; mientras que el segundo, E_b, contiene aristas (v_i,v_j) tales que i > j. Cada vértice se visita en orden v₁,v₂,…,v_|v|, relajando cada arista saliente de ese vértice en E_f. Cada vértice es, después, visitado en orden v_|v|,v_|v-1|,…,v₁, relajando cada arista saliente de ese vértice en E_b. La mejora de Yen reduce a la mitad, de manera efectiva, el número de “pases” requeridos para la solución del camino más corto desde una única fuente.

algoritmo de Bellman-Ford (camino máximo)

El problema de la ruta más larga puede ser transformado en el de ruta más corta cambiando el signo de los costes de los arcos. De manera alternativa se puede transformar también cambiando los procesos de inicialización y relajación. En este caso el problema es inconsistente para circuitos de peso positivo.

Inicializar
    for cada v perteneciente a V[G]
        do d[v] = - infinito
            p[v] = nulo
    p[s] = 0
Relajación
        if d[v] < d[u] + w(u,v) then 
            d[v] = d[u] + w(u,v)
            p(v) = u

Puede encontrar más información en:

Richard E. Bellman
L. R. Ford Jr.
Delbert Ray Fulkerson prize
Bellman, R. E., On a routing problem, quarterly of Applied Mathematics, 16, 87-90, 1958.
Ford, L. R.Jr., Network Flow Theory, Paper P-923, RAND Corporation, Santa Monica, California, 1956.

ejemplo de camino mínimo

El proceso de utilización y la interpretación de los resultados es exactamente la misma que en el caso del algoritmo de Dijkstra. Tras construir el grafo, se de seleccionar un nodo origen y un nodo destino antes de ejecutar el algoritmo. Los resultados deberían ser los mismos que en el caso del algoritmo de Dijkstra, pero puede ocurrir que el grafo tenga varias soluciones óptimas y que cada uno de estos algoritmos muestre una de ellas.

En el ejemplo sencillo utilizado anteriormente, ambas soluciones coinciden en el mismo camino de mínimo coste 7 unidades.

ejemplo de camino mínimo con Bellman-Ford

Arcos calculados desde el nodo origen (0) hasta el nodo destino (4):

 *   0 ----(5)---> 3
 *   3 ----(2)---> 4

Coste total = 7

Matriz de Arcos con coste mínimo:

N1\N2 0 1 2 3 4 
0 0 0 0 1 0 
1 0 0 0 0 0 
2 0 0 0 0 0 
3 0 0 0 0 1 
4 0 0 0 0 0


El Algoritmo de Borůvka es un algoritmo para encontrar el mínimo árbol de expansión en un grafo ponderado en el que todos sus arcos tienen distinto peso.

Fue publicado por primera vez en 1926 por Otakar Borůvka como un método eficiente para construir la red eléctrica de Moravia.¹ ² El algoritmo fue redescubierto porChoquet en 1938;³ de nuevo por Florek, Łukasiewicz, Perkal, Steinhaus y Zubrzycki en 1951; y de nuevo por Sollin a principio de la década de 1960. Debido a queSollin fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado Algoritmo de Sollin, especialmente en la literatura sobrecomputación paralela.

Algoritmo

El algoritmo comienza examinando cada vértice y añadiendo el arco de menor peso desde ese vértice a otro en el grafo, sin tener en cuenta los arcos ya agregados, y continua uniendo estos grupos de la misma manera hasta que se completa un árbol que cubra todos los vértices. Si denominamos a cada vértice o conjunto de vértices conectados como «componente», el pseudocódigo del Algoritmo de Boruvka es:

Comenzar con un grafo conexo G en el que todos sus arcos tengan distinto peso, y un conjunto vacío de arcos T.
Mientras los vértices de G conectados por T sean disjuntos:
Crear un conjunto vacío de arcos S
Para cada componente:
Crear un conjunto vacío de arcos S
Para cada vértice v en el componente:
Agregar el arco de menor peso desde el vértice v a otro vértice en un componente disjunto a S


Añadir el arco de menor peso en S a E


Añadir el conjunto resultante E a T.


El conjunto de aristas resultante T es el árbol de expansión mínimo de G.


Complejidad

Con el Algoritmo de Boruvka se puede obtener una complejidad de  $O(\log(V))$  $O(\log(V))$  iteraciones en el bucle externo antes de terminar, y por lo tanto su complejidad temporales  $O(E\log(V))$  $O(E\log(V))$ , donde  $E$  $E$  es el número de arcos, y  $V$  $V$  es el número de vértices de  $G$  $G$ . En grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de nodos después de cada etapa del algoritmo.⁴

Otros algoritmos

Entre otros algoritmos para este problema se incluyen el Algoritmo de Prim (realmente descubierto por Vojtech Jarnik) y el Algoritmo de Kruskal. Algoritmos más rápidos pueden ser obtenidos combinando el Algoritmo de Prim con el Algoritmo de Boruvka.

El algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a Karger, Klein y Tarjan y se obtiene una complejidad  $O(E)$  $O(E)$ .

El mejor algoritmo (determinista) conocido para encontrar el árbol mínimo de recubrimiento de Bernard Chazelle está también basado en parte en el Algoritmo de Boruvka y tiene complejidad temporal  $O(E\alpha (V))$  $O(E\alpha (V))$ , donde  $\alpha$  $\alpha$  es la inversa de la Función de Ackermann. Estos algoritmos aleatorios y deterministas combinan pasos del Algoritmo de Boruvka reduciendo el número de nodos que quedan por conectar, con pasos de diferente tipo que reduzcan el número de arcos entre cada par de nodos.



Algoritmo de Boruvka

Este algoritmo se dio a conocer hacia 1926 como un método eficiente para construir la red eléctrica de Moravia (República checa)

El algoritmo de Boruvka o de Sollin hace parte de los diferente algoritmos de búsqueda de caminos mínimos.

- CARACTERISTICAS:


- ES un algoritmo con una velocidad de convergência (o resolución) bastante rápida siendo ideal para implementación en ordenadores paralelos ya que la Minimum Spanning Tree de cada uno de los subgrafos puede ser calculada en una máquina diferente.


- Este algoritmo es recursivo y sólo termina cuando existe sólo un vértice. El algoritmo de Boruvka obtiene un árbol recubridor mínimo en un grafo G ponderado y conexo (no se admiten ponderaciones negativas).


- El algoritmo de Boruvka consiste en elegir desde cada vértice la arista de menor peso que sale de él, y así formar al inicio un conjunto de componentes de vértices unidos por dichas aristas.


- A partir de entonces en cada paso se busca la arista de menor peso entre los vértices de cada componente y un vértice que no lo sea, es decir, cada componente se unirá a otra distinta. El algoritmo termina cuando todos los vértices del grafo pertenecen a la misma componente.


- PASOS DEL ALGORITMO DE BORUVKA

El algoritmo de Boruvka consiste en elegir desde cada vértice la arista de menor peso que sale de él, y así formar al inicio un conjunto de componentes de vértices unidos por dichas aristas es decir el algoritmo comienza examinando cada vértice y añadiendo el arco de menor peso desde ese vértice a otro en el grafo, sin tener en cuenta los arcos ya agregados, y continua uniendo estos grupos de la misma manera hasta que se completa un árbol que cubra todos los vértices. Si denominamos a cada vértice o conjunto de vértices conectados como "componente", el Algoritmo de Boruvka es:

Comenzar con un grafo conexo G en el que todos sus arcos tengan distinto peso, y un conjunto vacío de arcos T.
Mientras los vértices de G conectados por Tsean disjuntos:
Crear un conjunto vacío de arcos S
Para cada componente:
Crear un conjunto vacío de arcos S
Para cada vértice v en el componente:
Agregar el arco de menor peso desde el vértice v a otro vertice en un componente disjunto a S


Añadir el arco de menor peso en S a E


Añadir el conjunto resultante E a T.






El conjunto de aristas resultante T es el arbol de expansión mínimo de G.


- COMPLEJIDAD

Con este algoritmo se puede obtener una complejidad de O(log(V)) iteraciones en el bucle externo antes de terminar, y por lo tanto su complejidad temporal es O(Elog(V)), donde E es el numero de arcos, y V es el numero de vertices de G.
En grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de nodos despues de cada etapa del algoritmo.