Algoritmos y Estructuras de Datos (VJ1215)

En la versión del algoritmo de Dijkstra que aparece en este apartado "Using a priority queue" de la página "Dijkstra's algorithm", se realizan estas operaciones con la cola de prioridad en el peor caso:

• O(|V|) veces add_with_priority (insertar)

• O(|V|) veces extract_min (consultar y eliminar el mínimo)

• O(|E|) veces decrease_priority (disminuir prioridad)

El coste temporal del algoritmo depende del coste de esas operaciones. El resto de cosas que hace el algoritmo no son más costosas. Y el coste de esas operaciones depende de cómo se implemente la cola de prioridad, cuya talla es O(|V|). Considerando que hacemos lo necesario para poder acceder en tiempo O(1) al elemento al que le queremos disminuir la prioridad (es decir, para que no haya que buscarlo en la cola de prioridad):

1. Si la cola de prioridad se implementa utilizando un vector no ordenado:

   • add_with_priority cuesta O(1)

   • extract_min cuesta O(|V|)

   • decrease_priority cuesta O(1)

   Por tanto, el coste total del algoritmo es O(|V| + |V|² + |E|) = O(|V|²).

2. Si la cola de prioridad se implementa utilizando un montículo binario:

   • add_with_priority cuesta O(log |V|)

   • extract_min cuesta O(log |V|)

   • decrease_priority cuesta O(log |V|)

   Por tanto, el coste total del algoritmo es O(|V| log |V| + |V| log |V| + |E| log |V|). Si consideramos que existe al menos un arco por vértice cuando aplicamos al algoritmo de Dijkstra, el coste es O(|E| log |V|).

Cuál de esas dos implementaciones es mejor para este algoritmo depende de cómo sea el grafo. Considerando estas dos situaciones extremas:

1. Si |E| = O(|V|), el grafo se denomina disperso. Es lo que sucede, por ejemplo, si cada vértice está conectado mediante un arco con a lo sumo 4 vecinos. En ese caso, el coste del algoritmo con un montículo binario es menor que con un vector no ordenado.

2. Si |E| = O(|V²|), el grafo se denomina denso. Es lo que sucede, por ejemplo, si cada vértice está conectado mediante un arco con la mitad de los demás vértices. En ese caso, el coste del algoritmo es menor (e inmejorable) con un vector no ordenado.

Existen otras implementaciones posibles. Para saber más, mira también:

• La página 13 de las transparencias "Greedy Algorithms II" de Kevin Wayne (ahí n=|V| y m=|E|; el algoritmo analizado está en la página 12, con una notación diferente pero equivalente a la de la Wikipedia).

• Los últimos 7 párrafos del apartado 9.3.2 "Dijkstra's Algorithm" en el libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss, o en la antigua edición en castellano "Estructuras de datos y algoritmos" (1995).

• El ejercicio 29 del tema 1.