ValueError: dictionary update sequence element while implementing Breadth First Search

Question

I am trying to port Breadth First Search to input graph as a dictionary of dictionary values:

Input graph:

graph = {'A': {'B':'B', 'C':'C'},
         'B': {'A':'A', 'D':'D', 'E':'E'},
         'C': {'A':'A', 'F':'F'},
         'D': {'B':'B'},
         'E': {'B':'B', 'F':'F'},
         'F': {'C':'C', 'E':'E'}}

Python program

def dictSub(d1,d2):
    return {key: d1[key] - d2.get(key, 0) for key in d1.keys()}

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in dictSub(graph[vertex], dict(zip([path,path]))):
            # print graph[vertex] - set(path)
            print graph[vertex]
            print set(path)
            print vertex
            raw_input()
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

print shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']

Problem

So this is the source code from this tutorial. It runs well if the original source code is used. When I am trying to implement this I ran into:

Traceback (most recent call last):
  File "./bfsTest.py", line 66, in <module>
    print shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
  File "./bfsTest.py", line 62, in shortest_path
    return next(bfs_paths(graph, start, goal))
  File "./bfsTest.py", line 49, in bfs_paths
    for next in dictSub(graph[vertex], dict(zip([path,path]))):
ValueError: dictionary update sequence element #0 has length 1; 2 is required

What have I tried:

1. dictionary update sequence element #0 has length 3; 2 is required

2. Error: "dictionary update sequence element #0 has length 1; 2 is required" on Django 1.4

Please feel free to suggest any better way to achieve this. Please don't suggest to change my data structure (It's a requirement).

Answer 1

The error comes from dict(zip([path, path])), it should be dict(zip(path, path))

Also, your dictSub function should look like this:

def dictSub(d1,d2):
    return {key: d1[key] for key in d1.keys() if key not in d2}

Alternatively, you could simplify the code using set arithmetics

def bfs_paths(graph, start, goal):
    graph = {k: set(v) for k, v in graph.items()}
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in (graph[vertex] - set(path)):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))