Algoritmos de caminos mínimos en grafos

A continuación les mostrare otros dos algoritmos para poder encontrar el camino corto en un grafo.

Una sucesión de aristas adyacentes que empieza en v y termina en w es un camino de v a w.

Mientras G=(V,A) un grafo ponderado, u, v vértices de G. Le encontramos distancia de u a v, d(u,v), a la mínima longitud de los caminos que unen u con v. Cuando no existe camino de u a v se dice que d(u,v)= infinito.

Dado un grafo ponderado y dos vértices s y t queremos encontrar d(s,t) y el camino con dada longitud.

Si el vértice u se encuentra en un camino C de longitud mínima entre los vértices s y z entonces, la parte de C comprendida entre los vértices s y u es un camino de longitud mínima entre s y u. Por lo tanto, el conjunto de caminos mínimos desde s a los restantes vértices del grafo G es un árbol, llamado el árbol de caminos mínimos desde s.

Algoritmo de Dijkstra

La idea principal de este algoritmo consiste en: Si P es un camino de longitud mínima s--z y P contiene al vértice v, entonces la parte s--v de P es también camino de longitud mínima de s a v. Esto indica que si queremos determinar el camino óptimo de s a cada vértice z de G, podremos hacerlo en orden creciente de la distancia d(s,z).

'                                                        Imagen que representa la ejecución del algoritmo de Dijkstra.

Características del algoritmo
Entrada: Un grafo ponderado, un vértice s que pertenece a V. El peso de la arista uv indicada por w(uv), colocando w(uv)= infinito si uv no es arista. (Las aristas no tienen pesos negativos).

Clave: Mantener el conjunto T de vértices para el camino más corto y incrementar T hasta que T=V. Para esto etiquetamos cada vértice z con t(z) que es la longitud del camino más corto ya encontrado. Así mantenemos un conjunto A de vértices que se encuentran en el árbol de búsqueda pero no en el árbol de camino mínimo y que son alcazables desde los vértices de T.

Inicialización: Sea A={s}, T{}, t(s)=d(s,s)=0, t(z)= infinito para z diferente de s.

Iteración: Elegimos el vértice v que pertenece a A con etiqueta mínima. Añadimos v a T. Designamos v como "vértice actual" y eliminarlo de A.

Analizar cada arista vz con z no perteneciente de T y actualizamos la etiqueta de z a min{t(z), t(v)+w(vz)}. Y añadimos z a A.

La iteración continua hasta que T=V(G) o hasta que t(z)= infinito para cada vértice z no perteneciente a T

En cualquier caso la etiqueta de cada vértice z en T será la distancia de s a z. En el segundo caso los vértices que no están en T no son alcanzable desde s.

Análisis asintótico

Complejidad del algoritmo: O(|V|2+|E|) = O(|V|2) sino utilizamos cola de prioridad, O((|E|+|V|) log |V|) cuando utilizamos la cola de prioridad (ejemplo un montículo).

Podemos apreciar la complejidad computacional del algoritmo de Dijkstra en términos de sumas y comparaciones. El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se agrega un vértice al conjunto señalado. Para apreciar el número total de operaciones tenemos que valorar  el número de operaciones llevadas a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en Sk realizando n-1 comparaciones o menos. Después hacemos una suma y comparamos para actualizar la etiqueta de cada uno de los vértices que no están en Sk. Por lo tanto, en cada iteración se realizan 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas faltantes de actualizar en cada iteración. Si no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, hemos llegado al siguiente teorema. 

Indica que el Algoritmo de Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para poder  determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

Pseudocódigo ejemplo (encontrado).

DIJKSTRA (Grafo G, nodo_fuente s)       

       para u ∈ V[G] hacer

           distancia[u] = INFINITO

           padre[u] = NULL

       distancia[s] = 0

       Encolar (cola, grafo)

       mientras que cola no es vacía hacer

           u = extraer_minimo(cola)

           para v ∈ adyacencia[u] hacer

               si distancia[v] > distancia[u] + peso (u, v) hacer

                   distancia[v] = distancia[u] + peso (u, v)

                   padre[v] = u

                   Actualizar(cola,distancia,v)

Algoritmo de Ford-Fulkerson

Es una variante del algoritmo de Dijkstra que permite asignar pesos negativos en las aristas, aunque no permite la existencia de ciclos de peso negativo en el grafo.

Algoritmo de etiquetado de Ford y Fulkerson sirve para el cálculo del flujo máximo de una red.

Características del algoritmo
Entrada: Un grafo ponderado con pesos que no son negativos en las aristas, un vértice s que pertenece a V. El peso de la arista uv se indica por w(uv), colocando w(uv)= infinito si uv no es arista.

Salida: La distancia desde s a cada vértice del grafo.

Clave: Mejorar en cada paso las etiquetas de los vértices, t(u).

Inicialización: Sea T={s}, t(s)=d(s,s)=0, t(z)= infinito para z diferente de s.

Iteración: Mientras existan aristas e=xz para los que t(z)>t(x) + w(e) actualizaremos la etiqueta de z a min{t(z), t(x)+w(xz)}.

Análisis asintótico

Tenemos que observar que cada arista se puede considerar varias veces. Empezamos ordenando las aristas del grafo D siendo este el orden en que se considerarán las aristas en el algoritmo. Después de la primera pasada se repite el proceso hasta que en una pasada completa no se produzca ningún cambio de etiquetas. Si D no tiene ciclos negativos se puede demostrar que, si el camino mínimo s ---> u contiene k aristas entonces, después de k pasadas alcanzamos la etiqueta definitiva para u. Como k <= n y el nº de aristas es q, resulta que la complejidad del algoritmo de Ford es O(qn). Incluso de puede detectar un ciclo negativo si se produce una mejora en las etiquetas en la pasada número n.

Pseudocódigo ejemplo (encontrado)

Ford-Fulkerson(G,s,t)

 { 

  for (cada arco (u,v) de E) 

  { 

   f[u,v]= 0; 

   f[v,u]= 0; 

  } 

  while (exista un camino p desde s a t en la red residual Gf) 

  { 

    cf(p) = min{cf(u,v): (u,v) está sobre p};

    for (cada arco (u,v) en p) 

    { 

      f[u,v]= f[u,v] + cf(p); 

      f[v,u]= - f[u,v]; 

    }  

  } 

 }

Referencias:

Algoritmo de Dijkstra
Algoritmo de Ford-Fulkerson