Как бы вы модифицировали BFS, чтобы найти кратчайший путь от A до B, учитывая, что график очень большой?

Что я подразумеваю под «очень большим графом», заключается в том, что каждая вершина имеет 1000 соседних вершин, но если вы идете, чтобы увидеть окончательное решение, расстояние от A до B было всего 6 ( сказать).

В такой ситуации использование базового алгоритма BFS будет расточественным, поскольку он ставит все 1000 соседних вершин А, а затем в следующем раунде 1000 для каждого из них и так далее. 1000 ^ 6 вершин ..

Любая идея, как оптимизировать? Или, скорее, есть ли путь?