Algoritmo de Dijkstra usando un montón

Question

Mi maestro me dio un pseudocódigo de Dijkstra el algoritmo binario montón incluyendo los siguientes pasos (x sólo fue extraído de la pila):

Para cada vértice y que es un nodo en un montón y hay una arista (x,y) en un gráfico:

1) Dist[y] = min(Dist[y], Dist[x] + w(x,y))

2) Actualización de la información y del nodo en el montón

También se dice que la complejidad de estos pasos para que todo algoritmo es O(ElogV).

Pero yo no entienda por qué el paso ", que es un nodo en un montón de" no influye en la complejidad de la mala manera. Porque eso significa que tenemos que encontrar todos los vecinos de x en el montón, pero no hay formas eficientes de búsqueda de nodos en la pila (sólo lineal de la búsqueda viene a mi mente), y esto significa que para cada y debemos:

1) Buscar en el montón - que toma O(número de nodos en la pila) relojes

2) Actualización de la información - que toma O(logV) tiempo

De esta manera, se llevará a S V*E*logV+(V-1)*E*logV+...) = O($V^2$*E*logV), ya que el número de nodos en la pila disminuye en cada paso por 1. Estoy perdiendo algo?

Answer 1

Uno puede almacenar una matriz de indicadores, uno para cada nodo, que apunta a la ubicación del vértice en el montón utilizado en el de Dijkstra el algoritmo. Cuando cada montón de operación se aplica (por ejemplo, la eliminación del elemento de la parte superior), uno puede fácilmente actualizar esta matriz para cada operación de intercambio en la memoria que así está hecho. (Así que uno puede definir una modificación montón de estructura de datos de tal manera que cada elemento en la pila tiene una clave (es decir, un puntero), y uno puede encontrar inmediatamente el elemento en la pila de una clave determinada, incluso si el montón de cambios). De esta manera, si desea buscar un nodo en el montón, usted no necesita hacer una búsqueda lineal, pero acabo de comprobar que el puntero del nodo.