Algoritmos de resolución de problemas de Caminos Mínimos en Grafos

En esta lección aprenderemos el desarrollo y funcionamiento de algunos de los algoritmos más populares para la resolución de problemas de Caminos Mínimos en Grafos.

Aunque no nos será útil en el desarrollo de nuestra aplicación, ya que plantearemos el problema de caminos mínimos en grafos como un problema de programación lineal, veremos el funcionamiento de algunos de los algoritmos más populares, descritos anteriormente, a la hora de hallar el camino mínimo entre dos o más vértices de un grafo:

  • Algoritmo de Dijkstra:

Este algoritmo resuelve el problema de hallar el camino más corto entre un vértice fijado como origen y cualquier otro vértice de un grafo con aristas ponderadas con pesos positivos minimizando el peso total de las aristas elegidas en el camino.

Como solución obtendremos la ponderación total del camino mínimo desde el vértice de origen a cualquier otro vértice del grafo pero no así los nodos por los cuales tenemos que pasar para realizar ese camino aunque podríamos ir anotándolos en caso de que lo necesitáramos a medida que transcurre el algoritmo, en este caso lo omitiremos porque en el caso en que tengamos muchos vértices en el grafo el algoritmo se vuelve muy largo y lento gastando recursos innecesarios de memoria.

Pasos del algoritmo:

Partimos un grafo con nodos \(x_0,\ldots,x_{n-1}\), \(n\in\mathbb{N}\) y fijamos un origen \(x_0\). Intentaremos rellenar un vector \(D\) de \(n\) componentes, donde \(n\) es el número de vértices de nuestro grafo, con las ponderaciones más pequeñas desde \(x_0\) a cada uno de los vértices restantes.

  1. La primera componente de nuestro vector será \(0\) ya que \(d(x_0,x_0)=0\) y suponemos que el resto de componentes tienen un valor inicial de \(+\infty\).
  2. Nos situamos en el nodo \(a=x_0\).
  3. Recorremos los restantes vértices adyacentes al nodo \(a\) los cuales denotamos como \(x_a^1,\ldots,x_a^{r_a}\) con \(r_a\in\mathbb{N}\) y comparamos, si \(D_{x_a^j}>D_a+d(a,x_a^j)\) para algún \(j=k\in\{1,\ldots,r_a\}\) establecemos \(D_{x_a^j}=D_a+d(a,x_a^j)\) y procedemos a realizar la misma comparación para \(j=k+1\) si \(k<r_a\). Cuando \(j=r_a\) paramos de realizar este paso.
  4. Descartamos el nodo \(a\).
  5. Tomamos, si es posible, como nuevo nodo \(a\) actual aquel tal que se alcance \(\min \{D_{x_i} : x_i \mbox{ no ha sido descartado para } i\in\{0,\ldots,n-1\}\}\).
  6. Repetimos el proceso desde el paso 3 si hemos encontrado algún posible nodo \(a\). Si no hemos podido encontrar ningún posible nodo \(a\) hemos terminado. Las componentes del vector que se encuentren al finalizar el proceso a valor \(+\infty\) indican que no existe ningún camino en el grafo desde \(x_0\) hasta el nodo de dicha componente.

  • Algoritmo de Bellman-Ford:

Este algoritmo resuelve el problema de hallar el camino más corto entre un vértice fijado como origen y cualquier otro vértice de un grafo con aristas ponderadas con pesos positivos o negativos minimizando el peso total de las aristas elegidas en el camino.

Como solución obtendremos la ponderación total del camino mínimo entre todos los vértices del grafo pero no así los nodos por los cuales tenemos que pasar para realizar ese camino análogamente al algoritmo de Dijkstra.

La diferencia con respecto al algoritmo anterior la encontramos en que en este caso somos capaces de detectar la existencia en el grafo de ciclos negativos (el peso total de las aristas del ciclo es negativo) que impiden que termine el algoritmo de Dijkstra.

Pasos del algoritmo:

Partimos un grafo con nodos \(x_0,\ldots,x_{n-1}\), \(n\in\mathbb{N}\) y fijamos un origen \(x_0\). Intentaremos rellenar un vector \(D\) de \(n\) componentes, donde \(n\) es el número de vértices de nuestro grafo, con las ponderaciones más pequeñas desde \(x_0\) a cada uno de los vértices restantes.

  1. La primera componente de nuestro vector será 0 ya que \(d(x_0,x_0)=0\) y suponemos que el resto de componentes tienen un valor inicial de \(+\infty\).
  2. Recorremos todas las aristas \((x_i,x_j)\) con \(i,j\in\{1,\ldots,n\}\) del grafo y comparamos, si \(D_{x_j}>D_{x_i}+d(x_i,x_j)\) establecemos \(D_{x_j}=D_{x_i}+d(x_i,x_j)\).
  3. Realizamos el proceso anterior \(n-1\) veces.
  4. Si somos capaces de volver a relajar alguna arista, es decir, si para alguna arista del grafo \((x_i,x_j)\) se cumple que \(D_{x_j}>D_{x_i}+d(x_i,x_j)\) entonces hemos encontrado un ciclo negativo y terminamos el proceso ya que no existe un camino mínimo entre el origen y algún vértice del grafo.
  5. Si no hemos acabado en el paso 4, hemos encontrado el camino mínimo entre el origen y cualquier otro nodo del grafo.

  • Algoritmo de Floyd-Warshall:

Este algoritmo resuelve el problema de hallar el camino más corto entre todos los vértices de un grafo con aristas ponderadas con pesos positivos minimizando el peso total de las aristas elegidas en el camino.

Como solución obtendremos la ponderación total del camino mínimo entre todos los vértices del grafo pero no así los nodos por los cuales tenemos que pasar para realizar ese camino análogamente a los algoritmos anteriores.

Pasos del algoritmo

Partimos un grafo con nodos \(x_1,\ldots,x_n\), \(n\in\mathbb{N}\).  Intentaremos rellenar una matriz \(D\) de \(n^2\) componentes, donde \(n\) es el número de vértices de nuestro grafo, con las ponderaciones más pequeñas desde \(x_i\) a \(x_j\) en la posición \(D_{ij}\).

  1. Rellenamos con 0 la diagonal principal de la matriz \(D\) ya que \(d(x_i,x_i)=0\) para todo \(i\in\{1,\ldots,n\}\).
  2. Fijamos dos vértices \(x_i\) y \(x_j\), con \(i,j\in\{1,\ldots,n\}\) siendo \(i\neq j\).
  3. Realizaremos un proceso recursivo, calcularemos el \(\mbox{CaminoMinimo}(i,j,k)\) como el camino más corto entre los vértices \(x_i\) y \(x_j\) usando los vértices \(x_1,\ldots,x_k\) teniendo en cuenta que el camino mínimo entre \(x_i\) y \(x_j\) se encontrará en estos vértices o será la concatenación entre los caminos mínimos de \(x_i\) a \(x_{k+1}\) y de \(x_{k+1}\) a \(x_j\). Para ello:
    1. Fijamos \(\mbox{CaminoMinimo}(a,b,0)\) como el peso de la arista \((x_a,x_b)\) para \(x_a,x_b\in\{x_1,\ldots,x_n\}\) siendo el peso \(0\) de la arista \((x_a,x_a)\) para todo \(a\in\{1,\ldots,n\}\)  (consideraremos este peso como \(+\infty\) si esta arista no existe).
    2. Fijamos \(\mbox{CaminoMinimo}(a,b,k)=+\infty\) para algún \(k\in\{1,\ldots,n\}\) si no existe ningún camino que vaya de \(x_a\) a \(x_b\) usando los vértices \(x_1,\ldots,x_k\).
    3. Calculamos desde \(k=1\) hasta \(k=n\) \(\mbox{CaminoMinimo}(i,j,k)\) de manera recursiva como \(\mbox{CaminoMinimo}(i,j,k)=\min\mbox{(CaminoMinimo}(i,j,k-1),\) \(\mbox{CaminoMinimo}(i,k,k-1)+\mbox{CaminoMinimo}(k,j,k-1))\).
    4. Establecemos \(D_{ij}=\mbox{CaminoMinimo}(i,j,n)\).
  4. Realizamos el proceso desde el paso 2 para cada par de vértices \(x_i,x_j\) del grafo con \(i,j\in\{1,\ldots,n\}\) siendo \(i\neq j\).

Última modificación: viernes, 22 de junio de 2018, 18:39