使用广度优先搜索返回最短路径

Question

我有一个 graph:

graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

确定我的结束节点的函数：

def person_is_seller(name):
  return name[-1] == 'm' # thom is the mango seller

以及广度优先搜索算法：

from collections import deque

def search(name):
  search_queue = deque()
  search_queue += graph[name]
  searched = set()

  while search_queue:
    # print(search_queue)
    person = search_queue.popleft()
    if person not in searched:
      # print(f'Searching {person}')
      if person_is_seller(person):
        return f'{person} is a mango seller'
      else:
        search_queue += graph[person]
        searched.add(person)
  return f'None is a mango seller'

search('you')
# 'thom is a mango seller'

我想知道这个算法是否可以return从you到thom的最短路径？

[you, claire, thom] # as this is the shortest path to thom which is my end node

我检查了this answer and it states that it does not let me find the shortest path but the second answer states that it is possible to provide the shortest path, I assume without using Djikstra's algorithm。所以我有点困惑，我能否以某种方式跟踪前一个节点，如果到达最终节点，请提供最短路径，如上一个代码片段或任何其他格式？

Answer 1

你可以searched一个字典而不是一个集合，然后让每个键的值成为你来自的节点的反向引用。

当您找到目标时，您可以通过返回这些反向引用然后 return 反向操作来恢复路径。

改编代码：

def search(name):
  search_queue = deque()
  search_queue.append((name, None))
  searched = {}  # dict instead of set

  while search_queue:
    # print(search_queue)
    person, prev = search_queue.popleft()
    if person not in searched:
      searched[person] = prev
      # print(f'Searching {person}')
      if person_is_seller(person):
        result = []
        while person is not None:
            result.append(person)
            person = searched[person]
        return result[::-1]
      else:
        search_queue += [(neighbor, person) for neighbor in graph[person]]
  return []

现在函数 return 是一个列表。找到路径时它将具有开始和结束节点，因此在这种情况下：

['you', 'claire', 'thom']

如果找不到路径，则结果为空列表。

Answer 2

只要每条边的长度相同，就可以使用BFS来寻找最短路径。当不同的边具有不同的权重时，Dykstra算法是必要的。

纯形式的 Dykstra 算法仅计算最短路径的长度。由于您可能想要最短路径本身，因此您需要将每个访问过的节点与边缘另一端的节点相关联，这通常使用关联数组（Python 中的“字典”）完成.

使用广度优先搜索返回最短路径

Returning shortest path using breadth-first search

python

algorithm

breadth-first-search