Кратко — какие критерии выбирать и почему, с доказательствами корректности и оценкой сложности.

1) Критерии выбора $обобщённо$

Если граф не взвешен $всерёбраимеют«одинаковый»вес,либоинтересуетминимумчисларёбер$ → BFS $одинисточник$ или многопроходный BFS $несколькоисточников$.Если взвешен, веса неотрицательные → Dijkstra $быстрый$.Если возможны отрицательные веса и нужно корректно обработать их $и/илиобнаружитьотрицательныециклы$ → Bellman–Ford.Если нужно только проверка достижимости, обход всех вершин, компоненты связности, построение порядка при DAG → DFS $илиBFSдлянекоторыхзадач$.Для топологической сортировки DAG → Kahn $BFS-подобный$ или DFS $поубываниювремениокончания$.Если нужны кратчайшие пути между всеми парами вершин: для dense графа — Floyd–Warshall; для sparse с возможными отрицательными весами без негативных циклов — Johnson $перевесить+Dijkstra$.Практические соображения: для очень больших разреженных графов использовать Dijkstra с кучей $heap$; для плотных графов Dijkstra с матрицей/масивом может быть эффективнее $O(V^2)$. Bellman–Ford обычно дороже $O(VE)$, но прост в реализации и даёт обнаружение отрицательных циклов.

2) BFS $обходвширину$. Применение

Невзвешенные графы: кратчайший путь по числу рёбер.Поиск достижимости, минимальное число шагов, многоточечные волны.

Доказательство корректности $кратко$

BFS строит слои: расстояние dist$$v$$ = уровень, на котором v впервые получен. По индукции: все вершины на расстоянии k по числу рёбер обнаруживаются не позднее уровня k. При извлечении из очереди мы обрабатываем вершины в порядке увеличения уровня, поэтому никакая вершина не будет получена с меньшим числом рёбер позже. Следовательно, полученные dist — оптимальны по числу рёбер.

Сложность

O$V+E$ времени и O$V$ дополнительной памяти $очередь+массивvisited/dist$.

3) DFS $обходвглубину$. Применение

Проверка достижимости, компоненты связности $внеориентированном$, поиск мостов/точек сочленения, топологическая сортировка $черезвременаокончания$.Подходит, когда порядок обхода важен или нужно получать структуру рекурсивных вызовов.

Доказательство корректности $длятопологическойсортировкичерезвременаокончания$

Если в DAG есть ребро u → v, то в ходе DFS либо v полностью обойдётся в вызове DFS$v$ до того, как закончится DFS$u$ (тогда finish(v) < finish(u)), либо DFS$u$ не начался до DFS$v$. В любом случае finish$u$ > finish$v$. Следовательно, упорядочение по убыванию времени окончания даёт топологический порядок $предшественникиидутраньшепотомков$.

Сложность

O$V+E$ времени, O$V$ памяти $стекрекурсииилиявныйстек$.

4) Алгоритм Дейкстры. Применение

Взвешенный граф, все веса рёбер ≥ 0, нужен кратчайший путь от одного источника.Практически: карты/роуд-нейтворки — веса $дистанции/время$ неотрицательны → Dijkstra $илиA\ast еслиестьэвристика$.

Доказательство корректности $классическое«жадное»утверждение$

Инвариант: когда вершина u извлекается из приоритетной очереди $имеяминимальноетекущееdist$, её dist окончателен $неизменитсяпозднее$.Доказательство по противоречию: пусть u извлечена с dist$$u$$ = d, но существует путь s → ... → u с суммарным весом d' < d. Рассмотрим первый по пути вершину x ещё не извлечённую $т.е.первый«незакреплённый»послеизвлечённых$; её dist ≤ d' < d, значит очередь должна была извлечь x раньше u. Противоречие. Неотрицательность весов требуется, чтобы при прохождении от извлечённых вершин к не извлечённым расстояния не уменьшались «неожиданно» через уже обработанные вершины.

Сложность

С реализацией через бинарную кучу: O$(V+E)logV$ ≈ O$ElogV$ для связных графов.С использованием Fibonacci-кучи: O$E+VlogV$ $редкоиспользуетсявпрактике$.С матрицей смежности $илибезкучи$: O$V^2$ — удобно для плотных графов.

5) Bellman–Ford. Применение

Наличие отрицательных весов $нотребуетсяотсутствиенегативногоцикланадостижимыхвершинах,еслинужноконечноерешение$.Нужна детекция отрицательных циклов, или несколько источников через добавление фиктивного источника.

Доказательство корректности

Любой простой путь содержит ≤ V−1 рёбер. Если после k итераций релаксации всех рёбер все кратчайшие пути, состоящие не более чем из k рёбер, корректно найдены.Индукция: после 0 итераций dist либо 0 $источник$ либо ∞. При очередной полной итерации релаксации всех рёбер корректно обновляются все пути длиной ≤ k+1, так как путь длиной k+1 разбивается на путь длиной k плюс одно ребро; если длина пути минимальна, то длина пути к предпоследней вершине была уже минимальной после k итераций. Следовательно, после V−1 итерации найдены все оптимальные расстояния.Для обнаружения отрицательного цикла достаточно сделать ещё одну итерацию: если какой-то dist уменьшается, значит есть цикл, позволяющий уменьшать суммарный вес бесконечно $отрицательныйцикл$.

Сложность

O$V\cdot E$ времени, O$V$ памяти. Для больших графов часто дорог.

6) Топологическая сортировка $применениеикорректность$

Применение: упорядочение задач с зависимостями $DAG$.Методы: Kahn $удалениевершинсindegree=0$ или DFS $обратныйпорядококончаний$.Корректность Kahn: в DAG всегда есть вершина с indegree=0 $иначецикл$. Удаляя такие вершины и их рёбра, получаем корректный порядок; если в процессе нет доступных вершин, значит есть цикл.Оба метода работают за O$V+E$.

7) Практические рекомендации и дополнительные замечания

Карты/навигация: Dijkstra $илиA\ast сэвристикой$ — быстрый, веса неотрицательны. Для быстрого многопоиска $множествоисточников/целей$ использовать многопоточность, bidirectional Dijkstra, предварительную маршрутизацию $ALT,contractionhierarchies$.Сети с отрицательными весами: Bellman–Ford, либо Johnson $перевещивание$: запускаем Bellman–Ford один раз с фиктивным источником, получаем потенциалы h$v$, затем ребра перевешиваем: w'$u,v$=w$u,v$+h$u$−h$v$ ≥ 0, и запускаем Dijkstra из каждой вершины $еслинужноall-pairs$, что даёт общую сложность O$VE+V\cdot ElogV$ ≈ O$VE+V\cdot ElogV$ — выгодно для разреженных графов.Если нужно обнаружить отрицательные циклы — Bellman–Ford прямо даёт инструмент.Для очень больших графов и спецзадач рассмотрите эвристики и индексирование $ALT,CH$ или приблизительные алгоритмы.

8) Резюме $короткиекритерии$

Невзвешенный → BFS.Взвешенный, веса ≥ 0 → Dijkstra $heap$ $еслимногозапросов—рассмотретьпредобработку/индексацию$.Взвешенный, возможны отрицательные веса → Bellman–Ford $дляsingle-source+обнаружениециклов$ или Johnson $дляall-pairs$.Топологический порядок в DAG → Kahn или DFS.По сложности: BFS/DFS/topo O$V+E$; Dijkstra O$ElogV$ $илиO(V^2)$; Bellman–Ford O$VE$.

Если хотите, могу привести формальные доказательства $полныешагииндукции$ для каждого алгоритма в более развернутом виде, либо схемы реализации и примеры кода для конкретных задач $карты,сетисотриц.весами,DAG$.