Supongo que ha estudiado el algoritmo de Dijkstra y cómo se implementan las colas de prioridad mínima, por ejemplo, utilizando un montón dinámico binario. Para obtener descripciones de montones binarios, puede consultar un buen libro de texto o buscar en Internet.
Este PDF (Página en princeton.edu) tiene buenas explicaciones (con ilustraciones gráficas) de cómo funcionan los montones binarios (y otras variantes más sofisticadas). Lo encontré buscando en Google. Puede encontrar referencias aún mejores en Internet.
En el algoritmo de Dijkstra, el paso importante es seleccionar un vértice inexplorado v de manera que haya un borde (u, v) en el gráfico, donde u es un vértice ya explorado, y d ‘(v) = dist (u) + costo ( u, v) es mínimo. Aquí, dist (u) es la longitud de la ruta más corta ya encontrada desde el vértice fuente s hasta el vértice u , y el costo (u, v) es el peso del borde de u a v .
- ¿Cómo podemos solucionar esto?
- ¿Vale la pena pagar 6 x $ 49 por una estructura de datos y especialización de algoritmos en Coursera?
- ¿Qué significa "algo"?
- ¿Cómo las aplicaciones como el Partometer 3D calculan la longitud en 3D usando la cámara y la entrada táctil?
- Algoritmos: ¿Qué sucede cuando un usuario crea una matriz de tamaño -100, qué sucede en la memoria?
Si almacenamos los vértices inexplorados en una matriz simple / lista vinculada, tendríamos que iterar sobre toda la lista cada vez para encontrar el vértice deseado v, con un mínimo de d ‘(v) ( d’ (v) = dist (u) + costo (u, v) ).
Si almacenamos los vértices en una cola de prioridad con d ‘(v) como clave para cada vértice, podemos obtener el vértice con un mínimo de d’ (v) mediante la operación Extract-Min . Si usamos un montón binario (min-), la complejidad asintótica de la operación Extract-Min será O (log n) .
Después de seleccionar el vértice v y actualizar dist (v) , podemos encontrar que tenemos una ruta más corta a otro vértice inexplorado w a v , es decir, una ruta con costo d ‘(w) = dist (v) + costo (v, w ) , que es menor que el costo de la ruta existente a w .
Este vértice estará en la cola de prioridad, y su valor clave deberá cambiarse al nuevo valor utilizando la operación Decrease-Key , que disminuirá la clave de un determinado elemento y lo burbujeará si es necesario para garantizar el mínimo propiedad del montón. Un montón binario (min) apoyará la operación de Decrease-Key con complejidad O (log n) .
Nuevamente, si hubiéramos usado una lista simple, este paso nos habría requerido iterar sobre la lista completa para actualizar la clave de un vértice.
Además, existen otras estructuras de datos que se pueden usar para implementar una cola prioritaria de manera más eficiente, como los montones binomiales y los montones de Fibonacci. Pero estos vienen a expensas de la complejidad añadida.
