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

Question

#广度优先搜索

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

- vernonnn

Answer 1

由于所有边的权重都相同或没有权重，您可以应用BFS以以下方式找到最短路径 - 第一次遇到节点意味着到该节点的路径是最短的，因此对于每个已访问的顶点，您可以维护导致它的前一个顶点，然后在遇到目标顶点时恢复路径：

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')    

- Guru Stron