7.20. El algoritmo de Dijkstra¶
El algoritmo que vamos a utilizar para determinar la ruta más corta se llama el “algoritmo de Dijkstra”. El algoritmo de Dijkstra es un algoritmo iterativo que nos proporciona la ruta más corta desde un nodo inicial particular a todos los otros nodos en el grafo. De nuevo, esto es similar a los resultados de una búsqueda en anchura.
Para llevar un seguimiento del costo total desde el nodo inicial a cada destino, utilizaremos la variable de instancia dist en la clase Vertice. La variable de instancia dist contendrá la ponderación total actual de la trayectoria de menor ponderación desde el inicio hasta el vértice en cuestión. El algoritmo itera una vez por cada vértice del grafo; sin embargo, el orden en que iteramos sobre los vértices es controlado por una cola de prioridad. dist es el valor que se usa para determinar el orden de los objetos en la cola de prioridad. Cuando se crea un vértice, a dist se le asigna un número muy grande. Teóricamente, a dist se le asignaría infinito, pero en la práctica simplemente asignamos un número que sea mayor que cualquier distancia real que pudiéramos tener en el problema que estamos tratando de resolver.
El código para el algoritmo de Dijkstra se muestra en el Programa 1. Cuando el algoritmo termine, las distancias estarán asignadas correctamente así como lo estarán los enlaces a los predecesores para cada vértice en el grafo.
Programa 1
from pythoned.grafos import ColaPrioridad, Grafo, Vertice
def dijkstra(unGrafo,inicio):
cp = ColaPrioridad()
inicio.asignarDistancia(0)
cp.construirMonticulo([(v.obtenerDistancia(),v) for v in unGrafo])
while not cp.estaVacia():
verticeActual = cp.eliminarMin()
for verticeSiguiente in verticeActual.obtenerConexiones():
nuevaDistancia = verticeActual.obtenerDistancia() \
+ verticeActual.obtenerPonderacion(verticeSiguiente)
if nuevaDistancia < verticeSiguiente.obtenerDistancia():
verticeSiguiente.asignarDistancia( nuevaDistancia )
verticeSiguiente.asignarPredecesor(verticeActual)
cp.decrementarClave(verticeSiguiente,nuevaDistancia)
El algoritmo de Dijkstra utiliza una cola de prioridad. Quizás usted recuerda que una cola de prioridad está basada en el montículo que implementamos en el capítulo sobre árboles. Hay un par de diferencias entre esa implementación sencilla y la implementación que usamos aquí para el algoritmo de Dijkstra. En primer lugar, la clase ColaPrioridad almacena tuplas de parejas clave-valor. Esto es importante para el algoritmo de Dijkstra ya que la clave en la cola de prioridad debe coincidir con la clave del vértice en el grafo. En segundo lugar, el valor se utiliza para decidir la prioridad y, por tanto, la posición de la clave en la cola de prioridad. En esta implementación usamos la distancia al vértice como la prioridad ya que, como veremos cuando exploremos el vértice siguiente, siempre queremos explorar el vértice que tenga la menor distancia. La segunda diferencia es la adición del método decrementarClave. Como podrá notar, este método se utiliza cuando se decrementa la distancia a un vértice que ya está en la cola, y por lo tanto ese vértice se mueve hacia el frente de la cola.
Miremos una aplicación del algoritmo de Dijkstra, un vértice a la vez, usando la siguiente secuencia de figuras como referencia. Comenzamos con el vértice \(u\). Los tres vértices adyacentes a \(u\) son \(v, w,\) y \(x\). Dado que las distancias iniciales a \(v, w,\) y \(x\) están todas inicializadas a sys.maxint, los nuevos costos para llegar a ellos a través del nodo de inicio son todos sus costos directos. Así que actualizamos los costos a cada uno de estos tres nodos. También asignamos \(u\) al predecesor para cada nodo y agregamos cada nodo a la cola de prioridad. Utilizamos la distancia como clave para la cola de prioridad. El estado del algoritmo se muestra en la Figura 3.
En la siguiente iteración del ciclo while examinamos los vértices que son adyacentes a \(x\). El vértice \(x\) es el siguiente porque tiene el costo total más bajo y, por lo tanto, se movió hasta el principio de la cola de prioridad. En \(x\) miramos a sus vecinos \(u,v,w\) y \(y\). Para cada vértice vecino verificamos si la distancia a ese vértice a través de \(x\) es menor que la distancia conocida previamente. Obviamente éste es el caso de \(y\) ya que su distancia era sys.maxint. No es el caso de \(u\) ni de \(v\) ya que sus distancias son 0 y 2 respectivamente. Sin embargo, ahora sabemos que la distancia a \(w\) es menor si pasamos por \(x\) que desde \(u\) directamente a \(w\). Dado que éste es el caso, actualizamos \(w\) con una nueva distancia y cambiamos el predecesor para \(w\) de ser \(u\) a ser \(x\). Mire la Figura 4 para ver el estado de todos los vértices.
El paso siguiente es mirar los vértices vecinos de \(v\) (ver la Figura 5). Este paso no produce cambios en el grafo, por lo que pasamos al nodo \(y\). En el nodo \(y\) (ver la Figura 6) descubrimos que es más barato llegar a ambos \(w\) y \(z\), por lo que ajustamos las distancias y los enlaces predecesores de acuerdo con ello. Finalmente verificamos los nodos \(w\) y \(z\) (ver la Figura 6 y la Figura 8). Sin embargo, no se encuentran cambios adicionales y por lo tanto la cola de prioridad está vacía y el algoritmo de Dijkstra termina.
Es importante tener en cuenta que el algoritmo de Dijkstra funciona sólo cuando todas las ponderaciones son positivas. Convénzase de que el algoritmo nunca terminaría si usted introduce una ponderacion negativa en una de las aristas del grafo.
Notemos que para enrutar mensajes a través de Internet, se utilizan otros algoritmos para encontrar la ruta más corta. Uno de los problemas con el uso del algoritmo de Dijkstra en el caso de Internet es que usted debe tener una representación completa del grafo para que el algoritmo funcione. La implicación de esto es que cada enrutador debería tener un mapa completo de todos los enrutadores en Internet. En la práctica, éste no es el caso y otras variaciones del algoritmo permiten que cada enrutador descubra el grafo sobre la marcha. Uno de tales algoritmos, sobre el cual usted quizá quiera leer, se llama el algoritmo de enrutamiento del “vector de distancias”.