Fare Dijkstra senza priority queue, letteralmente; vediamo perché.
Questo grafo è completo, pertanto |E|=\mathcal{O}(|V|^2). La complessità di Dijkstra con la priority queue è \mathcal{O}((|E|+|V|)\log |V|)=\mathcal{O}(|V|^2\log |V|).
Ora analizziamo cosa succede se al posto di usare una priority queue cerchi il minimo scorrendo tutti gli elementi.
Per ogni arco aggiorni al massimo una distanza nell’array delle distanze, dunque tutti gli aggiornamenti delle distanze sono \mathcal{O}(|E|)=\mathcal{O}(|V|^2). Invece una singola ricerca del minimo richiede \mathcal{O}(|V|), e questa va effettuata al più |V| volte (infatti se hai visitato tutti i nodi l’algoritmo termina, e con la ricerca lineare puoi garantire di trovare sempre un nuovo nodo a meno che tutti i nodi raggiungibili siano già stati visitati).
Allora anche questa parte, e quindi tutto l’algoritmo, sono \mathcal{O}(|V|^2), che risulta essere un miglioramento rispetto alla complessità ottenuta con la priority queue.
Questo genere di ottimizzazione è abbastanza comune quando devi lavorare con grafi densi.