Коротко сформулирую основные утверждения, затем докажу корректность BFS для невзвешенного графа, оценю сложности и сравню с Дейкстрой, в конце — конкретный пример, где BFS неприменим, а нужен Дейкстра.

1) Что делает BFS

BFS (поиск в ширину) от исходной вершины s обходит вершины «по слоям»: сначала все вершины на расстоянии 0 (s), затем на расстоянии 1 (смежные с s), затем на расстоянии 2, и т. д. Расстояние здесь — число рёбер в пути.

2) Доказательство, что BFS на невзвешенном графе даёт кратчайшие пути по числу рёбер

Инвариант: когда вершина v впервые извлекается из очереди (или «открывается»), её расстояние dist[v] равно минимальному числу рёбер в пути s → v.Доказательство по индукции по расстоянию d = dist[v]:
База d = 0: только s имеет расстояние 0, и это верно.Индукционный шаг: допустим, для всех вершин с расстоянием ≤ d инвариант верен. Рассмотрим вершину u, которую BFS обнаруживает и помечает расстоянием d (т. е. u впервые ставится в очередь с dist[u] = d). Это значит, что u найден как сосед некоторой вершины x с dist[x] = d − 1, причём x была извлечена раньше (по FIFO). Возможно существование пути с < d рёбрами в s → u? Тогда какая-то вершина y на этом пути на расстоянии d − 1 от s была бы обнаружена раньше и её соседи бы рассмотрены раньше, следовательно u была бы обнаружена раньше с расстоянием ≤ d − 1 — противоречие. Значит нет пути с меньшим числом рёбер, и dist[u] = d минимально.Следовательно при первом посещении каждой вершины BFS назначает ей минимальное по числу рёбер расстояние, а восстановленный по предшественникам путь действительно кратчайший по числу рёбер.

3) Сложности (для представления графа списками смежности)

Временная сложность: O(V + E). Каждая вершина помещается/извлекается из очереди не более одного раза, каждое ребро рассматривается ровно один раз (в ненаправленном графе можно считать два раза, что всё равно O(E)).Память: O(V) для массива visited/dist/parent и O(V) для очереди, итого O(V) (плюс память на представление графа O(V+E)).

4) Дейкстра: применение и сложности

Назначение: поиск кратчайших путей по сумме весов рёбер в графе с неотрицательными весами.Требование: веса рёбер должны быть неотрицательными (если есть отрицательные веса, Дейкстра может давать неверный результат).Временная сложность (зависит от структуры данных):
с бинарной кучей (priority queue): O((V + E) log V) ≈ O(E log V) для связных графов;с Фибоначчиевой кучей: O(E + V log V) (теоретически лучше на разрежённых графах);с матрицей смежности и без кучи: O(V^2) (эффективно для очень плотных графов).Память: O(V) для массивов расстояний и предков плюс память для кучи (до O(V)) и представления графа.

5) Сравнение применимости и ограничений

BFS полезен/корректен, когда все рёбра имеют одинаковый «вес» (обычно считаем единичным). Тогда кратчайший путь по сумме весов совпадает с кратчайшим по числу рёбер, и BFS — оптимальный и простой метод (O(V+E)).Дейкстра необходим, когда веса рёбер разные и важна сумма весов (но веса должны быть ≥ 0). Дейкстра сложнее по времени, но правильно учитывает разные веса.Если веса принимают только значения 0 и 1, есть специальный вариант 0-1 BFS (deque), который работает за O(V + E) и комбинирует преимущества BFS и деки.Если веса целые и небольшие — возможны алгоритмы типа Dial (кошики) с линейной по сумме за диапазон времени; если веса могут быть отрицательными — нужен Bellman–Ford (или Johnson + Дейкстра для всех пар).

6) Пример графа и задачи, где BFS неприменим, а Дейкстра необходим

Граф: три вершины A, B, C с рёбрами:
A → C, вес = 100A → B, вес = 1B → C, вес = 1Задача: найти кратчайший по сумме весов путь из A в C.Что сделает BFS (если его применить «как есть»): BFS ищет путь с минимальным числом рёбер. Он увидит прямое ребро A → C (1 ребро) и вернёт путь A → C (длина в рёбрах = 1).Но по сумме весов путь A → C весит 100, тогда как путь A → B → C весит 2 — он гораздо короче по сумме весов. Поэтому BFS даёт неправильный ответ для задачи «минимизировать сумму весов». Здесь нужен Дейкстра (он найдёт A → B → C с суммарным весом 2). (Если бы все рёбра были единичной стоимостью, то BFS был бы корректен.)Примечание: если есть отрицательные веса, даже Дейкстра неприменим — нужен Bellman–Ford.

Краткое резюме:

BFS = алгоритм для невзвешенных (или единично-взвешенных) графов, гарантирует минимальное число рёбер; время O(V+E), память O(V).Дейкстра = алгоритм для неотрицательно-взвешенных графов, минимизирует сумму весов; обычно медленнее (O(E log V) и т. п.), требует неотрицательных весов.Для задач с разными положительными весами (как в примере) BFS неприменим, требуется Дейкстра.