Объяснение
BFS обходит граф слоями с очередью и находит кратчайшее число рёбер в невзвешенном графе. Взвешенные рёбра требуют другого алгоритма; Дейкстра предполагает неотрицательные веса. Посещённость предотвращает бесконечный обход циклов.
Задача для самостоятельного решения
Для A→B, A→C, B→D, C→D найдите расстояние A–D.
Показать разбор ответа
BFS: очередь [A], затем [B,C], затем [D]. Расстояние равно 2. Помечайте вершину при добавлении в очередь, иначе D попадёт туда дважды.