Python 在广度优先搜索中查找最短路径的代码

发布于04月02日

#广度优先搜索

graph = {
    'S' : ['A','B'],
    'A' : ['B','C','D'],
    'B' : ['C'],
    'C' : ['D'],
    'D' : []
}
visited = []
queue = []
goal = 'D'
def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)
  while queue : 
    s = queue.pop(0)
    print(s, end = "\n")
    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)
        if goal in visited:
          break
bfs(visited,graph,'S')

#上述代码用于遍历路径.有谁能告诉我找到最短路径的密码.上述代码的输出为S A B C D

推荐答案

由于所有边都具有相同的权重或没有权重，因此可以通过以下方式应用BFS来查找最短路径-第一次遇到 node 时，这意味着到该 node 的路径是最短的，因此对于每个访问过的顶点，可以保留通向它的上一个顶点，然后在遇到目标顶点时恢复该路径:

visited_paths = {}
queue = []
goal = 'D'
def bfs(visited, graph, node):
  visited[node] = node # path to start includes start
  queue.append(node)
  while queue: 
    s = queue.pop(0)
    if(s == goal):
        break

    for n in graph[s]:
        if n not in visited:
            queue.append(n)
            visited[n] = s # set previous node when node is first encountered

  if goal in visited:
    # restore the path
    path = [goal]
    curr = goal
    while curr != node:
       curr = visited[curr]
       path.append(curr)
    path.reverse() # reverse path to get correct order
    print(path)
  else:
    print("No path")

bfs(visited_paths,graph,'S')