Ciao Gigi991,
l'algoritmo di Dijkstra avevo avuto modo di studiarlo con altri linguaggi di programmazione molti anni fa per poi lasciarlo.
Ho dato una veloce visita ai link proposti e mi sembrano interessanti. La logica implementativa ricorda quello che avevo fatto.
Forse ho trovato anche il post in cui si trattava dei 1700 nodi in 0.5/1 secondi, e sia l'OP che coloro che partecipavano a quella discussione dimenticavano che il ciclo for() non è pienamente consigliato per lavorare con gli array che invece è il foreach(). Tra l'altro non mi sembra che vi siano modifiche al grafo per esplicitarne la chiave scalare.
Trovo positiva l'idea di cache se fosse di possibile implementazione almeno per i percorsi comuni più richiesti.
Un suggerimento che mi sento di dare è quello di cercare di preferire l'esecuzione di un programma in C/C++ richiamato da PHP perché più performante rispetto all'esecuzione di quest'ultimo.
Se hai la possibilità limita il numero di richieste servibili contemporaneamente proprio per non mandare in crisi la RAM del server a causa delle ingenti risorse consumante dall'algoritmo in presenza di un grafo particolarmente complesso, oppure utilizza delle policy per favorire un certo tipo di utenza (per esempio quella pagante).
Probabilmente per questo specifico caso il top sarebbe quello di eseguirlo con un'applicazione tipo J2EE.
Buon lavoro e tienici informati sull'evoluzione.
