Complejidad temporal del algoritmo de Dijkstra con montículo mínimo y optimizaciones
¿Cuál es la complejidad temporal de esta implementación particular del algoritmo de Dijkstra?
Sé que varias respuestas a esta pregunta dicen que es O(E log V) cuando se utiliza un montón mínimo, y también lo dicen este artículo y este artículo. Sin embargo, este artículo dice que es O(V+ElogE) y tiene una lógica similar (pero no exactamente igual) al código de abajo.
Diferentes implementaciones del algoritmo pueden cambiar la complejidad temporal. Estoy tratando de analizar la complejidad de la implementación a continuación, pero las optimizaciones como verificar visitedSet e ignorar vértices repetidos en minHeap me hacen dudar de mí mismo.
Aquí está el pseudocódigo:
// esta parte es O(V)
for cada vértice en el grafo {
distanceMap[vértice] = infinito
}
// inicializar el vértice fuente
minHeap.add(vértice fuente y distancia 0)
distanceMap[fuente] = 0
visitedSet.add(vértice fuente)
// bucle a través de los vértices: O(V)?
mientras (minHeap no esté vacío) {
// Retirar del montón es O(log n) pero ¿n es el V o el E?
vértice y distancia = minHeap.removeMin
si (distancia > distancia guardada en distanceMap) continuar bucle while
visitedSet.add(vértice)
// bucle a través de las aristas: O(E) ?
para cada vecino de vértice {
si (visitedSet contiene vecino) continuar bucle for
totalDistance = distancia + peso al vecino
si (totalDistance < distancia guardada en vertexMap) {
// Agregar al montón es O(log n) pero ¿n es el V o el E?
minHeap.add(vecino y totalDistance)
distanceMap[vecino] = totalDistance
}
}
}
Notas:
- Cada vértice alcanzable desde el vértice fuente será visitado al menos una vez.
- Se verifica cada arista (vecino) de cada vértice, pero se ignora si está en
visitedSet. - Un vecino se agrega al montón solo si tiene una distancia más corta que la distancia actualmente conocida (se asume que las distancias desconocidas tienen una longitud predeterminada de infinito).
¿Cuál es la complejidad temporal real de esta implementación y por qué?
davy.ai
Basándose en el pseudocódigo proporcionado, la complejidad temporal de esta implementación particular del algoritmo de Dijkstra es O((V + E)logV).
El bucle inicial itera V veces y tiene una complejidad temporal de O(V).
El bucle principal itera el número de vértices (V) veces y, para cada vértice, puede iterar sobre todos sus vecinos (como máximo E veces). Verificar si un vecino ya está en el conjunto de visitados toma tiempo O(1), y agregar un vecino al montículo o actualizar su distancia en el mapa de distancias toma tiempo O(logV). Por lo tanto, la complejidad temporal del bucle principal es O(V logV + E logV).
En el peor caso, donde cada vértice está conectado a cada otro vértice, E puede ser tan grande como V2, lo que hace que la complejidad temporal sea O((V + V2)logV), que se simplifica a O(V2logV).
Por lo tanto, la complejidad temporal real de esta implementación es O((V + E)logV), teniendo en cuenta el peor escenario posible.