Как я могу найти кратчайший путь от любого узла до набора A

Question

У меня есть неориентированный граф 'G' и набор 'A' узлов в графе G

Я пытаюсь найти эффективный алгоритм, который находит кратчайшие пути из любого узла вграфик G до ближайшего узла в наборе 'A'

Я думал об этом: имея массив минимального расстояния до всех узлов, запустив алгоритм BFS на каждом узле в наборе A и после завершения BFS, обновите массивесли был найден более короткий путь, эта временная сложность составляет O (k (n + m)) - что очень много, когда K растет, мне сказали, что есть более эффективный алгоритм, который я могу использовать. Обратите внимание, что в этом упражнении мне разрешено использовать только алгоритм BFS

Answer 1

Создайте дополнительный узел, имеющий ребра для каждого узла в «А». Запустите BFS с этого дополнительного узла. Расстояние от каждого узла до ближайшего узла в «А» на 1 меньше расстояния до этого дополнительного узла.

Answer 2

Вам действительно нужен только один проход вашего алгоритма BFS, если вы начинаете со всех узлов с A в начальной очереди.

• отслеживает уже посещенные узлы и их пути к узламиз A в карте / словаре
• инициализируйте очередь BFS с кортежами (a, empty_path) для каждого узла a в вашем A наборе
• , в то время как в очереди больше элементов, попследующий узел и путь из очереди
• , если узел уже находится на карте visited, пропустите его
• , в противном случае добавьте его в visited с указанным путем
• добавить соседние узлы в очередь с расширенными путями

Пример на Python:

# 2--0--1
# |     |
# 3     4
graph = {0: [1, 2], 1: [0, 4], 2: [0, 3], 3: [2], 4: [1]}
A = [2, 0]

import collections
queue = collections.deque([(a, []) for a in A])
visited = {}
while queue:
    cur, path = queue.popleft()
    if cur in visited: continue
    visited[cur] = path
    for node in graph[cur]:
        queue.append((node, [cur] + path))
print(visited)
# {2: [], 0: [], 3: [2], 1: [0], 4: [1, 0]}