Anexo:Ejemplo de Algoritmo de Dijkstra
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
editarEl 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
editarSe 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
editarAhora, 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
editarSolución momentánea:
- Camino: ADCB
- Distancia:11
- Nodos procesados:A,D,C
Paso 4
editarComo 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
editarEn 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
editarEn 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
editarPor 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