Algoritmo de Dijkstra: Versión 1
(Determine el valor de f (n))
Los ciclos son bienvenidos, pero no se permiten distancias negativas)
Inicialización: k = 1; F (1) = 0; F (j) = Infinito, j = 2, …, n; U = {1, …, n} .Iteración: Mientras que ((k! = N) y (F (k) <infinito)) Hacer:
Actualización U: U = U \ {k}
Actualización F: F (j) = min {F (j), D (k, j) + F (k)}, j en U / \ S (k)
Actualización k: k = arg min {F (j): j en U}
Fin Do.
Esto significa que el algoritmo termina si la ciudad de destino n está próxima a procesarse (k = n) o F (k) = infinito. Esto último implica que en esta iteración F (j) = infinito para todas las ciudades j que aún no se han procesado y, por lo tanto, la conclusión es que no se puede llegar a estas ciudades desde la ciudad 1.
Tenga en cuenta que la formulación anterior del algoritmo no explica cómo se construyen los recorridos. Solo actualiza la duración de los recorridos. La construcción de tours se puede incorporar fácilmente en esta formulación al registrar el mejor predecesor inmediato de la ciudad que se está procesando. Este predecesor se actualiza sobre la marcha a medida que se actualiza F (j).
El resultado principal es el siguiente:
Teorema 1
El algoritmo de Dijkstra termina después de como máximo n-1 iteraciones. Si la matriz de distancia D no es negativa y el algoritmo termina porque k = n, luego de la terminación F (n) = f (n) y además F (j) = f (j) para todo j en C para el cual f (j ) <f (n). Si la terminación ocurre porque F (k) = infinito, entonces F (j) = f (j) para todo j en C para el cual f (j) <Infinito yf (j) = infinito para todas las demás ciudades.
En resumen, si las distancias entre ciudades no son negativas, el algoritmo produce los resultados deseados. El siguiente ejemplo ilustra el algoritmo en acción y destaca el hecho de que si se permite que las distancias sean negativas, el algoritmo puede generar una solución no óptima.
Ejemplo 1
La Tabla 1 muestra los resultados generados por el Algoritmo de Dijkstra para los dos problemas representados en la Figura 4. Los valores en las columnas k, U, F son los valores de los objetos respectivos al final de la iteración respectiva. La iteración 0 representa el paso de inicialización. 
D (i, j) 1 2 3 4 5 1 * 531092 ** 1 ** 3 *** 4 * 4 * 2 ** 15 ***** D (i, j) 1 2 3 4 5 1 * 531092 ** 1 ** 3 *** 7 * 4 * 2 ** – 35 ***** ab
Figura 4 Iteración k UF0– {1,2,3,4,5} (0, *, *, *, *) 11 {2,3,4,5} ( 0 , 5,3,10,9) 23 { 2,4,5} ( 0 , 5, 3 , 7,9) 32 {4,5} ( 0 , 5 , 3 , 7,9) 44 {5} ( 0 , 5 , 3 , 7 , 8) Iteración k UF0– {1,2,3,4,5} (0, *, *, *, *) 11 {2,3,4,5} ( 0 , 5,3,10,9) 23 {2, 4,5} ( 0 , 5, 3 , 10,9) 32 {4,5} ( 0 , 5 , 3 , 10,9) ab
tabla 1
Tenga en cuenta que en el caso (b) el algoritmo no pudo generar una solución óptima: F (n) = F (5) = 9> f (n) = f (5) = 7.
En cuanto a la complejidad computacional, el Algoritmo de Dijkstra funciona bastante bien. Para el análisis del peor de los casos, podemos dejar que S (j) = C = {1, …, n} y, por lo tanto, en la iteración m-ésima tenemos | U (m) | : = nm para los pasos Actualización F y Actualización k del algoritmo, donde | A | denota la cardinalidad del conjunto A. Por simplicidad, suponemos que la operación mínima en el paso Actualizar k se lleva a cabo ingenuamente por comparación por pares. Esto significa que en la iteración m-ésima, el paso Actualizar k requiere comparaciones nm-1. La Tabla 2 resume el número de adiciones y comparaciones realizadas en los pasos Actualización F y Actualización k del Algoritmo de Dijkstra en función de | U (m) | = nm, m = 1, …, n-1. Sumando estos valores sobre m = 1, …, n-1 produce el número total de operaciones realizadas por el algoritmo en el peor de los casos. Adiciones Comparaciones Actualización F (m) n-mn-m Actualización k (m) 0n-m-1 Total (m = 1,…, n-1) n (n-1) / 2n (n-1)
Tabla 2
Entonces, en el peor de los casos, el algoritmo ejecuta n (n-1) / 2 adiciones yn (n-1) comparaciones y, por lo tanto, la complejidad del algoritmo es O (n2). Sin embargo, debe tenerse en cuenta que se pueden usar estructuras de datos especiales (por ejemplo, montones y cubos ) para acelerar significativamente la operación “arg min” realizada por el paso Actualizar k del algoritmo (Denardo y Fox [1979], Gallo y Pallottino [1988 ], Bertsekas [1991], Ahuja et al [1993], Denardo [2003]).
En algún momento se requiere determinar la distancia más corta desde la ciudad 1 a cualquier otra ciudad j, j = 2,3, …, n. En este caso, la cláusula “While (…)” en la Versión 1 del algoritmo se puede cambiar a “While (| U |> 1 y F (k) <Infinito)". Esto produce la formulación más familiar del algoritmo: Algoritmo de Dijkstra: Versión 2
(Determine el valor de f (j), j = 1, …, n)
Los ciclos son bienvenidos, pero no se permiten distancias negativas. 
Inicializar: k = 1; F (1) = 0; F (j) = Infinito, j = 2, …, n
U = {1,2,3,…, n} Iterar: Mientras que (| U |> 1 y F (k) <infinito) Hacer: 
U = U \ {k}
F (j) = min {F (j), D (k, j) + F (k)}, j en U / \ S (k)
k = arg min {F (i): i en U} End Do.
Es posible que ahora desee experimentar con este algoritmo utilizando el Módulo 2. Tenga en cuenta que el módulo actualiza los valores de F (j) en dos pasos. Primero, los valores de G (k, j) = D (k, j) + F (k) se calculan para j en U / \ S (k) y luego los valores respectivos de F (j) = min {F ( j), G (k, j)} se calculan. Inicialice: F (1) = 0; F (j) = Infinito, j = 2, …, n
- ¿Cuáles son las ventajas de la agrupación de K-Means?
- ¿Cómo se ordenan las matrices para que los valores altos y bajos se distribuyan en diagonal?
- Cómo resolver el problema ADDGP en SPOJ
- ¿Por qué los programadores experimentados dicen que la programación del mundo real es completamente diferente a la programación competitiva?
- ¿Cuál es el mejor método de clasificación para usar si solo un elemento está fuera de servicio?
U = {1,2,3,…, n} Iterar: Mientras que (| U |> 1 y F (k) <infinito) Hacer:
U = U \ {k}
G (k, j) = D (k, j) + F (k), j en U / \ S (k)
F (j) = min {F (j), G (k, j)}
k = arg min {F (i): i en U} End Do.
Iteración No. j 1 2 3 4 5 6 7 8 9 10kUFD (k, j) G (k, j) Valores actualizados de U, F y k
U
F
k 
Ejemplo D (i, j) 1 2 3 4 5 6 7 8 9 10
1
2
3
4 4
5 5
6 6
7 7
8
9 9
10 Escasa 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Cíclico Acíclico
Módulo 2
Tenga en cuenta que el algoritmo termina cuando solo queda una ciudad por procesar (| U | = 1) y / o cuando F (j) es igual al infinito para todas las j en U. Esta última indica que todas las ciudades aún no se han procesado no son accesibles desde la ciudad 1.
