CODEWITHSUNDEEP
pythongraph-theoryshortest-path
Mohib
Mohib

Reputation: 43

Shortest path Graph BFS python

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

Upvotes: 1

Views: 1964

Answers (1)

user19055902
user19055902

Reputation:

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

Upvotes: 2

Related Questions