Количество путей минимальной длины от 1 до N, включая каждый узел
Учитывая неориентированный и невзвешенный граф из N узлов и M ребер, задача состоит в том, чтобы подсчитать пути минимальной длины между узлом 1 и N через каждый из узлов. Если такого пути не существует, то выведите «-1» .
Примечание . Путь может проходить через узел любое количество раз.
Примеры:
Input: N = 4, M= 4, edges = {{1, 2}, {2, 3}, {1, 3}, {2, 4}}
Output: 1 1 1 1
Explanation:
Total paths of minimum length from 1 to 4, passing from 1 is 1.
Total paths of minimum length from 1 to 4, passing from 2 is 1.
Total paths of minimum length from 1 to 4, passing from 3 is 1.
Total paths of minimum length from 1 to 4, passing from 4 is 1.Input: N = 5, M = 5, edges = {{1, 2}, {1, 4}, {1 3}, {2, 5}, {2, 4}}
Output: 1 1 0 1 1
Подход: данная проблема может быть решена путем выполнения двух BFS, одного из узла 1 , исключая узел N , и другого из узла N , исключая узел 1 , чтобы найти минимальное расстояние между всеми узлами из 1 и N и произведение обоих минимальных расстояний. будет общим количеством путей минимальной длины от 1 до N , включая узел. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте очередь, скажем, queue1 для выполнения BFS с узла 1 и очередь queue2 для выполнения BFS с узла N.
- Инициализируйте массивы, скажем, dist[] для хранения кратчайшего расстояния иways[] для подсчета количества способов добраться до этого узла.
- Выполните два BFS и выполните следующие шаги в каждом случае:
- Извлеките из очереди и сохраните узел в x и его расстояние в dis .
- Если dist[x] меньше, чем dis , продолжайте.
- Пройдите по списку смежности x и для каждого дочернего элемента y , если dist[y] больше, чем dis + 1 , тогда update dist[y] равно dis + 1 иways[y] равноways [x] . В противном случае, если dist[y] равно dis +1 , тогда добавьтеways [x] кways[y] .
- Наконец, выполните итерацию по диапазону N и для каждого узла выведите количество путей минимальной длины какways1[i]*ways2[i] .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N + M)
Вспомогательное пространство: O(N)