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

You use square brackets when pushing new items into the queue. Try replacing them with parentheses so you push tuples instead of lists. q.append((neighbor, distance+1)) — Locke
– Locke, Commented May 6, 2022 at 19:16
The problem is in the initial definition of q You need to initialize it with an iterable of what you want, so just do q = deque([(nodeA,0)]) — Amir
– Amir, Commented May 6, 2022 at 19:19

score 2 · Accepted Answer · 2022-05-11 07:48:49Z

2

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

edited May 11, 2022 at 7:48

answered May 6, 2022 at 19:26

user19055902

Sign up to request clarification or add additional context in comments.

1 Comment

Mohib Over a year ago

Thank you! Bad syntax on my end. Just to make it work temporary, I just appended in to the q instead of initializing at same time. But yours is more clean. So thanks!

Collectives™ on Stack Overflow

Shortest path Graph BFS python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related