Algoritmo de Dijkstra
EW Dijkstra (1930-2002) propuso en 1959 un algoritmo (llamado algoritmo de Dijkstra) que permite determinar la camino más corto entre dos vértices de un grafico conectado ponderado. El algoritmo de Dijkstra se basa en la siguiente observación: una vez que determinamos el camino más corto a un vértice v, entonces los caminos que van desde v a cada uno de sus vértices adyacentes podrían ser el camino más corto a cada uno de estos picos vecinos. El algoritmo de Dijkstra es un algoritmo de programación dinámica glotón, visita todas las soluciones posibles.
Condiciones
- Sin longitud negativa
- Arco o borde
- Número finito de vértices
- Una fuente (y, de paso, un objetivo) definida
El algoritmo de Dijkstra toma como entrada un gráfico dirigido ponderado por reales positivos y un vértice fuente. Se trata de construir progresivamente un subgrafo en el que se clasifican los diferentes vértices en orden creciente de su distancia mínima desde el vértice inicial. La distancia corresponde a la suma de los pesos de los bordes prestados.
Inicialmente, consideramos que las distancias de cada vértice al vértice inicial son infinitas a excepción del vértice inicial para el cual la distancia es 0. El subgrafo inicial es el conjunto vacío.
Durante cada iteración, elegimos fuera del subgrafo un vértice de distancia mínima y lo agregamos al subgrafo (se convierte en un vértice visitado). Luego, actualizamos las distancias de los vértices vecinos del agregado (los vértices están marcados). La actualización se realiza de la siguiente manera: la nueva distancia desde el vértice vecino es el mínimo entre la distancia existente y la obtenida sumando el peso del arco entre el vértice vecino y el vértice sumado a la distancia desde el vértice agregado.
Seguimos así hasta completar completamente el subgrafo (o hasta seleccionar el vértice de llegada). Ejemplo :
| distancia | a A | a B | a C | a D | a E | a F | a G | a H | tengo | a J |
|---|---|---|---|---|---|---|---|---|---|---|
| paso inicial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A (0) | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ | |
| B (85PARA) | – | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ | |
| F (165B) | – | 217 | ∞ | 173 | – | ∞ | ∞ | 415 | ∞ | |
| E (173PARA) | – | 217 | ∞ | – | – | ∞ | ∞ | 415 | 675 | |
| C (217PARA) | – | – | ∞ | – | – | 403 | 320 | 415 | 675 | |
| H (320VS) | – | – | 503 | – | – | 403 | – | 415 | ||
| G (403VS) | – | – | 503 | – | – | – | – | 415 | 487 | |
| Yo (415F) | – | – | 503 | – | – | – | – | – | 487 | |
| J (487H) | – | – | 503 | – | – | – | – | – | – | |
| D (503H) | – | – | – | – | – | – | – | – | – |
Por razones prácticas, la resolución del algoritmo de Dijkstra solo devuelve un vector que contiene el vértice visitado, la lista de predecesores (los vértices ya validados) y los valores de los caminos más cortos a todos los demás vértices. Lo que corresponde a una línea actual de la tabla presentada. Usando la columna de la izquierda, podemos crear un árbol caminos más cortos del vértice A a todos los vértices.
El vértice inicial es el camino más corto para llegar a sí mismo. Luego, calculamos todos los caminos de tamaño 1 a partir de este vértice, para validar el más corto. Por lo tanto, este camino es el camino más corto desde el vértice inicial porque no hay un borde de peso negativo. Por inducción, deducimos que el algoritmo siempre valida un camino más corto.
d [0] = 0, d [i] = infinito para cualquier vértice que no sea el origen
siempre y cuando'hay un vértice fuera del subgrafo PAG
elige un top Para fuera de PAG menor distancia d [a]
poner Para dentro PAG
para cada pico B fuera de PAG vecino de Para
d [b] = min (d [b], d [a] + peso (a, b))
fin
fin
volver d