Предположим, что у нас есть двунаправленный граф с V количеством вершин и E количеством ребер, где вес всех ребер равен 1. Теперь у каждой вершины есть исходный уровень, и предположим, что мы хотим достичьуровень L. Предположим, что мы начинаем с уровня 1. Когда наш уровень i, мы можем проходить только через вершины уровня 0 или уровня i.После прохождения вершины, имеющей уровень i, мы повышаемся на 1.
Теперь, учитывая начальную точку и целевой уровень, как мы вычисляем минимальные шаги (затраты), необходимые для достижения целевого уровня?
Я считаю, что эту проблему можно решить с помощью модифицированного алгоритма BFS.На данный момент я могу определить, существуют ли такие пути или нет, но я не смог рассчитать затраты.
Буду признателен за любую помощь и предложения.
Например, у нас есть граф с V = 5, E = 4, L = 3 и начальной точкой в вершине 0. Следующие строки являются уровнем каждой вершины:
0 NO-LEVEL
1 0
2 0
3 2
4 1
, и следующие следующие E-линии представляют края:
0 1
1 2
2 3
0 4
С этим входом выход должен быть: 5 (0-> 4-> 0-> 1-> 2-> 3).Однако мой код выводит 3 (0-> 1-> 2-> 3).
Я все еще не понимаю, как включить процесс 0-> 4-> 0 при подсчете расстояния.