Caminos mínimos en grafos - PM 2019/2020

Veamos a continuación el funcionamiento de algunos de los algoritmos previamente descritos:

• Algoritmo de Dijkstra

Dado un grafo dirigido ponderado \( \mathbf{x_{0},...,x_{n-1}} \)nodos no aislados y distintos, consideremos \( \mathbf{x_{0}} \) el nodo inicial, \(\textbf{D} \) un vector de tamaño \(\textbf{n} \) que guardará al final del algoritmo las distancias desde x hasta el resto de los nodos.

1. En primer lugar inicializamos todas las distancias en D con un valor infinito(ya que estas son desconocidas), exceptuando la de x, que obviamente sería 0 ya que \(\mathbf{d(x_{0},x_{0})=0}\).
2. Tomamos \(  \mathbf{a=x_{0}} \).
3.  A continuación recorremos todos los nodos adyacentes de \(\mathbf{a}\), excepto los marcados(luego se verá el por que), a los no marcados se les denotará por \(\mathbf{v_{i}}\).
4. Para el nodo actual, calculamos la distancia desde dicho nodo hasta sus vecinos usando la fórmula \(  \mathbf{dt(v_{i})=D_{a}+d(a,v_{i})} \) ; la distancia tentativa es la distancia que actualmente tiene el nodo en el vector D mas la distancia desde el nodo actual hasta el nodo \(v_{i}\). Si esta es menor que la almacenada en el vector, actualizamos el vector con la que acabamos de calcular.
5. Se marca como completo el nodo  \(  \mathbf{a} \).
6. Tomamos como próximo nodo actual el de menor valor en \(\mathbf{D}\), y regresamos al paso 3 mientras sigan existiendo nodos no marcados.

Una vez terminado el algoritmo, \(\mathbf{D}\) estará completamente lleno

• Bellman-Ford

El planteamiento inicial es exactamente igual que en el algoritmo de Dijkstra, pasemos pues directamente a los pasos:

1. En primer lugar inicializamos todas las distancias en D con un valor infinito(ya que estas son desconocidas), exceptuando la de x, que obviamente sería 0 ya que \(\mathbf{d(x_{0},x_{0})=0}\).
2.  Recorremos todas las aristas \(d(x_{i},x_{j}) \) con \(\mathbf{i,j \in{1,...n}}\) del grafo y comparamos si \( \mathbf{D_{x_{j}}>D_{x_{i}}+d(x_{i},x_{j})} \) igualamos \(\mathbf{D_{x_{j}}=D_{x_{i}}+d(x_{i},x_{j})}\).
3. Realizamos el proceso anterior \(n-1\) veces.
4.  Si fuésemos capaces de volver a relajar alguna arista habríamos encontrado un ciclo negativo y el proceso habría terminado ya que no existiría un camino mínimo entre el origen y algún vértice del grafo.
5. Si no hemos acabado en el paso 4, ya hemos terminado.

• Algoritmo de Johnson

Este algoritmo usa los dos algoritmos que hemos descrito anteriormente mediante el siguiente proceso:

1.  Se añade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de peso 0.
2. Ahora utilizamos el algoritmo de Bellman-Ford empezando por el nuevo vértice q, determinará para cada vértice v el peso mínimo \(h(v)\) del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye.
3.  Seguidamente, a las aristas del grafo original se les cambia el peso usando los valores calculados anteriormente: una arista de u a v con tamaño \(w(u,v)\), tendría el nuevo tamaño \(w(u,v)+h(u)-h(v)\)
4. Finalmente, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, usando el grafo con pesos modificados.