Алгоритм Дейкстры, чтобы найти кратчайший путь между двумя узлами в большом графе?

Question

Алгоритм Дейкстры говорит

Для данного исходного узла на графике алгоритм находит кратчайший путь между этим узлом и каждым другим

Я получил алгоритм, чтобы найти кратчайший путь между этим узлом и каждым другим.Но мой вопрос, если мне нужно найти кратчайший путь ч / б двух специфических узлов (скажем, N1 и N2) для большого графа, такого как Linkedin / Facebook, мне нужно рассчитать расстояние между этим узлом N1 и каждым другим узлом (пользователь, что означает миллиардпользователей) сначала в linkedin, сохраните его в кэш-памяти и затем возвращайте его из кэша всякий раз, когда задается вопрос о кратчайшем расстоянии между двумя узлами ч / б?
Алгоритм dijkstra работает лучше там или любой другой алгоритм, такой как BFS лучше имеет смысл там?

Я сталкивался с подобным вопросом Java - Найти кратчайший путь между 2 точками на взвешенной по расстоянию карте , но этот вопрос относится к очень небольшому выборочному набору и использует здесь алгоритм Дейкстры.

Answer 1

Я согласен, что алгоритм Дейкстры не лучший вариант для решения подобных проблем. Поскольку у вас нет весов, я не вижу причин, по которым вы должны усложнить решение. Простой BFS был бы идеальным для вас, и он был бы оптимальным.