для неотрицательных весов, Беллман — Форд для отрицательных, A* — когда есть оценка расстояния до цели.
Ключевые тезисы
- с двоичной кучей работает за O((V + E) log V) и требует неотрицательных весов.
- Беллман — Форд медленнее, зато переживает отрицательные рёбра и находит отрицательные циклы.
- A* — та же с эвристикой; при допустимой эвристике оптимальность сохраняется.
Видеолекции
Записи университетских курсов, где эта тема звучит. Тайм-кодов у них нет, поэтому открываются они с начала.
Связанные темы
Алгоритмы на графах
Graph Traversal85%
Обходы графа: семейство · Алгоритмы и структуры данныхЗонтичная тема: что общего у обоих обходов, как увидеть граф в задаче, где он не назван, и по каким двум вопросам выбирается обход. Сами обходы разобраны отдельно.
Breadth-First Search85%
Поиск в ширину · Алгоритмы и структуры данныхОбход слоями: сначала всё, до чего один шаг, потом — два. Первое посещение вершины оказывается кратчайшим путём, если все переходы равноценны.
Depth-First Search85%
Поиск в глубину · Алгоритмы и структуры данныхИдти вглубь до упора и возвращаться. Порядок завершения вершин даёт топологическую сортировку, три цвета — обнаружение циклов, откат состояния — перебор с возвратом.
Graph Basics85%
Основы графов · Графы и сетиВершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.
Centrality85%
Центральности · Графы и сетиМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.
PageRank85%
PageRank · Графы и сетиСтационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как признак.
Спрашивают на собеседовании: Самокат — Логистика и сроки доставки, 2ГИС — Геопоиск и навигация.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.