Tiempo de ejecución para el algoritmo de Dijkstra en una cola de prioridad implementada por ordenada lista/matriz

Question

Tengo curiosidad por saber cuál es el tiempo de ejecución del algoritmo en la cola de prioridad implementada por una lista/matriz ordenada. Sé que para una lista/matriz no ordenada es O ((n^2 + m)) donde n es el número de vértices y m el número de bordes. Por lo tanto, eso equivale a O (n^2) tiempo. Pero sería más rápido si utilicé una lista ordenada/matriz ... ¿Cuál sería el tiempo de ejecución? Sé que la extractomina sería un tiempo constante.

Answer 1

Bien, Vamos a repasar lo que necesitamos para el algoritmo de Dijkstra (para referencia futura, por lo general vértices y aristas se utilizan como V y E, por ejemplo O (VlogE)):
se fusionen todas las listas de adyacencia clasificadas: O (e)
Extracto mínima: O (1)
Disminución clave: O (V)
Dijkstra utiliza O (V) extraer operaciones mínimas, y O (e) disminuir operaciones clave, por lo tanto:
O (1) * O (V) = O (V)
O (E) * O (V) = O (EV) = O (V^2)
Tomando la porción más significativa asintóticamente:
El tiempo de ejecución asintótico eventual es O (V^2).
¿Se puede mejorar esto? Sí. Mire en montones binarios y mejores implementaciones de colas de prioridad.

Editar: De hecho, cometí un error, ahora que lo veo de nuevo. E no puede ser más alto que V^2, o en otras palabras E = O (V^2).
Por lo tanto, en el peor de los casos, el algoritmo que concluimos carreras en O (EV) es en realidad O (V^2 * V) == O (V^3)

Answer 2

utilizo SortedList http://blog.devarchive.net/2013/03/fast-dijkstras-algorithm-inside-ms-sql.html Se es más rápido aproximadamente 20-50 veces que ordenando Lista una vez por iteración