2 semplici soluzioni che si presentano immediatamente:
Precarica tutto tramite qualcosa come l'algoritmo di Johnson, o usa ogni volta un algoritmo di ricerca standard come hai suggerito - Dijkstra per esempio (che si riduce a semplice BFS, poiché il grafico non è pesato).
Il primo richiede troppa memoria / RAM da fare. Il secondo è proibitivamente lento. Quello che vuoi (probabilmente) è una soluzione ibrida che combina una precomputazione (probabilmente una lunga, ma che non richiede molta memoria), e un calcolo per query più breve.
Clustering
Un approccio potrebbe essere quello di raggruppare in qualche modo il grafico e calcolare le distanze tra i vertici di uscita dei cluster. Quindi un algoritmo di ricerca non considererebbe nemmeno i percorsi nei cluster (o piuttosto usa i percorsi minimi precalcolati tra le uscite), a meno che quel cluster contenga il punto iniziale o finale.
A-Star
Un altro è calcolare un'euristica e usare A * (o qualsiasi altra ricerca assistita dall'euristica). Hai detto che non hai alcuna informazione sul grafico, eccetto la connessione, quindi potresti aver bisogno di ideare e precompilare una tale euristica.
Una tale euristica potrebbe essere un "ordine n spanning graph" minimo. Probabilmente c'è un termine appropriato per questo, ma è passato troppo tempo dai miei giorni Uni, quindi spiegherò cosa intendo. Chiamo un "ordine n spanning graph" una collezione di vertici, in modo tale che qualsiasi vertice nel tuo grafico originale sia raggiungibile da qualche vertice in questa collezione tramite un percorso di lunghezza al massimo n.
Se hai una raccolta di questo tipo, insieme a una mappatura di Vertex -> closest vertex in spanning graph + distance to it e le distanze tra 2 punti qualsiasi nel grafico a spanning, hai una euristica:
The distance between two vertexes is at least the distance between their closest vertices in the spanning tree + distances to them - 2*n. (Why? Because the distance between the spanning vertices is at most the distance between A and B + distances to them).
Questa è un'euristica ammissibile, quindi A * farà un buon lavoro usandolo.
Più piccolo è l'ordine della raccolta, migliore è l'euristica e più veloce la ricerca. Ma ciò significa anche che il grafico spanning sarà più grande, e quindi avrai bisogno di una matrice più grande di distanze. Probabilmente inizierei con un grafico dell'ordine di 50 o giù di lì, ma puoi modificarlo a seconda della forma / natura esatta del grafico.
Ottimizza per il caso d'uso medio
Vale anche la pena notare che puoi ottimizzare non per il grafico che hai, ma per le domande che rispondi. Se sono in genere da calcolare precise ma a piccole distanze, è possibile che si desideri precalcolare alcuni, ma non tutti i valori (ad esempio, le distanze da ciascun nodo a qualsiasi cosa raggiungibile con 3 o meno passaggi?). Avresti bisogno di fallback su uno dei metodi sopra descritti in questo caso, ma potrebbe essere sufficiente.
Questo fa sorgere la domanda: la precisione totale è davvero necessaria per i percorsi più lunghi? Forse le specifiche possono essere rilassate in questo senso?