Shortest path Graph BFS python

Question

Trying to return the int for shortest path in a graph, using BFS. The idea is to use a q, append into the q as [node,distance] and then when we traverse increase distance and keep track of the count and when we hit our destination first time that means we found shortest path so we return that. But I got error " currNode,distance = q.popleft() ValueError: not enough values to unpack (expected 2, got 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

Deque takes an iterable of elements as input, you gave it a tuple so your deque will contains two elements instead of the expected one tuple of two elements.

fix line 2 into:

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

also here is a cleaner implementation of 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