Anexo:Ejemplo de Algoritmo de Dijkstra

Grafo inicial

Camino mínimo final

Hay diferentes algoritmos para hallar un camino de longitud mínima entre dos vértices de un grafo ponderado. Presentaremos un algoritmo descubierto por el físico neerlandés Edsger Dijkstra en 1959. La versión que descubriremos resuelve este problema para grafos ponderados no dirigidos si todos los pesos no son negativos. Este algoritmo puede adaptarse fácilmente para resolver problemas de caminos de longitud mínima en grafo dirigidos.

A este algoritmo se le llama Algoritmo de Dijkstra:

Ejemplo

El siguiente ejemplo se mostrara como se desarrollará con el fin de encontrar el camino más corto desde a hasta z:

Leyenda:

• Rojo: Aristas y vértices pertenecientes a la solución momentánea.
• Azul: Aristas y vértices candidatos.

Paso 1

Se escoge de los nodos adyacentes aquel que tiene una menor peso en la arista, en este caso, el nodo d. En d

• Distancia:5
• Nodos procesados:A

Paso 2

Ahora, vemos que se añade un nuevo candidato, el vértice e, y el vértice c, pero esta vez a través del d. Pero el camino mínimo surge al añadir el vértice c.

Solución momentánea:

• Camino: ADC
• Distancia:9
• Nodos procesados:A,D

Paso 3

Solución momentánea:

• Camino: ADCB
• Distancia:11
• Nodos procesados:A,D,C

Paso 4

Como podemos comprobar, se han añadido un candidato nuevo, el vértice f, a través del vértice b. El mínimo camino hallado en todo el grafo hasta ahora es el siguiente:

Solución momentánea:

• 'Camino: ADCBF
• Distancia:15
• Nodos procesados:A,D,C,B

Paso 5

En este antepenúltimo paso, se añaden tres vértices candidatos, los vértices g, z y e. Este último ya estaba pero en esta ocasión aparece a través del vértice f. En este caso el camino mínimo, que cambia un poco con respecto al anterior, es:

Solución momentánea:

• Camino: ADCBG
• Distancia:17
• Nodos procesados:A,D,C,B,F

Paso 6

En el penúltimo paso, vuelve a aparecer otro candidato: el vértice e, pero esta vez a través del vértice f. De todas formas, el camino mínimo vuelve a cambiar para retomar el camino que venía siguiendo en los pasos anteriores:

Solución momentánea:

• Camino: ADCBFE
• Distancia:18
• Nodos procesados:A,D,C,B,F,G

Paso 7

Por fin, llegamos al último paso, en el que sólo se añade un candidato, el vértice z a través del vértice e. El camino mínimo y final obtenido es:

Solución Final:

• Camino: ADCBFEZ
• Distancia:23
• Nodos procesados:A,D,C,B,F,G,E