Anexo:Ejemplo de Algoritmo de Dijkstra

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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 holandé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 algorimo 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[editar]

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

Dijkstrapaso0.jpg

Leyenda:

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

Paso 1[editar]

Dijkstrapaso1.jpg

En d

  • Distancia:5

Paso 2[editar]

Dijkstrapaso2.jpg

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

Paso 3[editar]

Dijkstrapaso4.jpg

Solución momentánea:

  • Camino: ADCB
  • Distancia:11

Paso 4[editar]

Dijkstrapaso5.jpg

Como podemos comprobar, se han añadido un candidato nuevo, el vértice g, 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

Paso 5[editar]

Dijkstrapaso6.jpg

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 enterior, es:

Solución momentánea:

  • Camino: ADCBG
  • Distancia:17

Paso 6[editar]

Dijkstrapaso7.jpg

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

Paso 7[editar]

Dijkstrapaso8.jpg

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