Найдите кратчайший маршрут от A до G по заданным стрелкам

Задание

## Условие Есть ориентированная схема с вершинами A, B, C, D, E и G. Разрешены только такие переходы: - A → B и A → C; - B → D; - C → D и C → E; - D → G; - E → B. Старт находится в A, выход — в G. Одну вершину нельзя посещать дважды. Найдите маршрут с минимальным числом переходов. Если кратчайших маршрутов несколько, выберите лексикографически первый: при первом различии предпочтительна более ранняя буква.

Объяснение

Поиск в ширину даёт два кратчайших маршрута по три перехода: A→B→D→G и A→C→D→G. Путь A→C→E→B→D→G допустим, но содержит пять переходов. Среди двух минимальных вариантов лексикографическое правило выбирает B перед C, поэтому единственный ответ по уточнённому условию — A→B→D→G.