Кратчайший путь в невзвешенном графе
Кратчайший путь в невзвешенном графе — это маршрут между двумя вершинами, содержащий минимальное число рёбер. Такой путь находят с помощью обхода в ширину: алгоритм рассматривает вершины послойно, поэтому первая найденная дистанция до вершины является минимальной.
Невзвешенный граф — это граф, в котором рёбра не имеют числовых весов: каждое ребро считается равноценным и его стоимость равна 1. Если нужно найти маршрут с минимальной суммой весов, применяют другие методы, например алгоритм Дейкстры. Понятие кратчайшего пути является частным случаем общего понятия кратчайшего пути.
Как работает поиск
Сначала в очередь помещают начальную вершину и присваивают ей расстояние 0. Затем из очереди по очереди извлекают вершины и добавляют в очередь ещё не посещённых соседей. Для каждого такого соседа записывают расстояние на 1 больше расстояния до текущей вершины. Вершины с расстояниями 0, 1, 2 и так далее образуют уровни поиска.
Пусть есть рёбра \(A-B\), \(A-C\), \(B-D\), \(C-E\), \(D-F\), \(E-F\). Из \(A\) поиск сначала посещает \(B\) и \(C\) на расстоянии 1, затем \(D\) и \(E\) на расстоянии 2, а \(F\) — на расстоянии 3. Поэтому кратчайшее расстояние от \(A\) до \(F\) равно 3. Один из кратчайших путей: \(A-B-D-F\).
В невзвешенном графе длина пути — это число рёбер, а не число вершин и не сумма каких-либо значений. Если между вершинами нет пути, расстояние считают бесконечным или отмечают как недостижимое.
Какое расстояние от начальной вершины до неё самой?
Главное
- Кратчайший путь в невзвешенном графе содержит минимальное число рёбер.
- Для его поиска используют обход в ширину, который посещает вершины по уровням.
- Расстояние до начальной вершины равно 0, а при переходе по ребру увеличивается на 1.