4.3.3. Problemas de caminos mínimos.
Orden de complejidad del algoritmo, con matrices de adyacencia:
- Inicialización: O(n).
- Ejecutar n-1 veces:
- Buscar el elemento con D[v] mínimo y S[v] falso: O(n).
- Actualizar los valores de los nodos candidatos: O(n).
- En total tenemos O(n2).
Con listas de adyacencia:
- Inicialización: O(n).
- La actualización de los candidatos se limita a los nodos que son adyacentes a v. En total la actualización se hace O(a) veces.
- La búsqueda del elemento sigue requiriendo O(n) pasos, por lo que el orden total sería O(n2).
- Podemos usar una estructura ordenada para guardar los nodos candidatos (por ejemplo un árbol binario). La búsqueda requiere O(log n) en cada paso, en total O(n*log n). Además, en la actualización un nodo podría cambiar de posición en el árbol, luego requiere O(a*log n).
- En total, requiere O((a+n)*log n). Si el grafo es conexo: O(a*log n).
- Esta modificación será adecuada cuando a<<n2.