Кратчайший путь поиском в ширину

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

Ваш пример

Вершины нумеруются от 1 до N, N ≤ 40; до 120 строк рёбер. Пустой список допустим; повторные рёбра не меняют расстояние.

Разбор примера

1 → 3 → 5 → 6

Расстояния в невзвешенном графе
ВершинаРасстояние от начала
10
21
31
42
52
63
  1. Начальной вершине присваиваем расстояние 0.
  2. Очередь обрабатывает все вершины одного слоя раньше следующего.
Длина пути в рёбрах
3
Достигнуто вершин
6

Метод и условия расчёта

Поиск в ширину посещает вершины по неубыванию расстояния в рёбрах. Первый найденный предок восстанавливает один кратчайший путь.

Вопросы по теме

Подходит ли поиск для разных весов рёбер?

Нет. Здесь каждое ребро имеет одинаковую стоимость 1. Для разных неотрицательных весов нужен другой алгоритм.

Что делать с несколькими кратчайшими путями?

Показываем один из них: соседей обходим по возрастанию номера. Равная длина других путей не означает ошибку.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.