Ich würde gerne noch einige Randbedingungen kenne. Ist der Graph statisch oder ändert der sich laufend. Wie oft sollen die kürzesten Wege berechnet werden (selten oder oft)?

Bei statischem Graphen und häufigen Abfragen würde es sich vermutlich lohnen, alle kürzesten Wegstrecken im Voraus zu berechnen und in einer großen DB-Tabelle (ca. 12,5 Millionen Wege) abzulegen. Eine konkrete Wegabfrage kann dann schnell per DB-Lookup beantwortet werden.

Bei dynamischem Graphen wird wohl ein aufwändiger iterativer Ansatz (Breitensuche) notwendig sein. Bereits besuchte Knoten (merhrfach erreichbar) können dabei ausgelassen werden, da sie ja über Umwege gefunden wurden.