Grafos

Algoritmo de Bellman-Ford

Grafos forma parte de un proyecto de investigación y desarrollo de aplicaciones informáticas de diseño modular orientadas hacia la docencia, investigación y labores profesionales de Ingeniería de Organización. Grafos contiene entre otras una DLL con el Algoritmo de Bellman-Ford:

Lester Randolph Ford es uno de los pioneros en el campo de la programación de flujos en grafos. Es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) y nació el 23 de septiembre de 1927. L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.

Al continuar los pasos de su padre Ford Jr. también hizo una enorme contribución al campo de las matemáticas. Su trabajo con Delbert Ray Fulkerson (14 agosto de 1924 - 10 Enero de 1976) ha puesto la base de casi toda la investigación en flujos de grafos. El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.

Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.

La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos.

 

Algoritmo de Bellman-Ford (camino mínimo)

Soluciona el problema de la ruta más corta o camino mínimo desde un nodo origen, de un modo más general que el Algoritmo de Dijkstra, ya que permite valores negativos en los arcos.

El algoritmo devuelve un valor booleano si encuentra un circuito o lazo de peso negativo. En caso contrario calcula y devuelve el camino mínimo con su coste.

Para cada vértice v perteneciente a V, se mantiene el atributo d[v] como cota superior o coste del camino mínimo desde el origen s al vértice v.

A continuación se muestra el pseudocódigo del Algoritmo:

Bellman-Ford (G,s)

Inicializar
    for cada v perteneciente a V[G]
        do d[v] = infinito
            p[v] = nulo
    p[s] = 0

for i=1 to V[G]-1
    do for cada arco (u,v) perteneciente a A[G]
        Relajación
        if d[v] > d[u] + w(u,v) then
            d[v] = d[u] + w(u,v)
            p(v) = u

for cada arco (u,v) chequea lazo de peso negativo
    do if d[v] > d[u] + w(u,v) then
        return FALSO 'el algoritmo no converge
return VERDADERO

Fuente: A. Rodríguez

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

Fuente: A. Rodríguez

más información

- Bellman-Ford Algorithm Time Complexity
- 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.
 

Creative Commons License Alejandro Rodríguez Villalobos