Ho implementato l'algoritmo di ricerca dei percorsi di Dijkstra in JavaScript e gran parte di esso comporta l'archiviazione delle distanze dai nodi e il recupero del più piccolo. Le distanze cambiano spesso e il più piccolo viene recuperato molto.
Attualmente sto utilizzando un elenco collegato ordinato , con articoli messi in ordine quando aggiunto.
C'è un modo più veloce?
Modifiche:
- Elenco collegato ordinato = prima il valore più basso.
- Ecco il codice: link
Aggiornamento:
Implementata la proposta di Arnaud di un Mucchio di Fibonacci. È stato da 32 a 85 volte più veloce con rendimenti decrescenti più grande è il set di dati.
Ho deviato dal vero heap di Fibonacci non eseguendo il consolidamento ogni volta che veniva rimosso un valore. Ho trovato in esecuzione una volta ogni 50 turni eseguiti meglio.
Il codice sorgente è qui: link