最短路径图 BFS python

Question

尝试使用 BFS return 图中的最短路径的 int。这个想法是使用一个 q，作为 [node,distance] 追加到 q 中，然后当我们遍历增加距离并跟踪计数时，当我们第一次到达目的地时，这意味着我们找到了最短路径，所以我们 return 那。但是我得到了错误“currNode,distance = q.popleft() ValueError: 没有足够的值来解压（预期 2，得到 1）"

def shortestPath(graph,nodeA,nodeB):
    q = deque((nodeA,0))
    visited = set(nodeA)

    while q:
        currNode,distance = q.popleft()
        if currNode == nodeB:
            return distance
        for neighbor in graph[currNode]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append([neighbor,distance+1])
            

    return -1

graph_three = {
    'w':['x','v'],
    'x':['w','y'],
    'y':['x','z'],
    'z':['y','v'],
    'v':['z','w']
}

print(shortestPath(graph_three,'w','z'))

Answer 1

双端队列将元素的可迭代作为输入，你给了它一个元组，所以你的双端队列将包含两个元素，而不是预期的两个元素的一个元组。

将第 2 行修改为：

q = deque([(nodeA,0)])

这里还有一个更简洁的 BFS 实现：

def shortestPath(graph, root, target):
    if root == target: return 0
    q = collections.deque(root)
    visited = set(root)
    distance = 0
    while q:
        for _ in range(len(q)):
            node = q.popleft()
            for neighbor in graph[node]:
                if neighbor == target:
                    return distance + 1
                elif neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
        distance += 1
    return -1

最短路径图 BFS python

Shortest path Graph BFS python

python

graph-theory

shortest-path