Get a path between graph nodes using breadth-first search
I don't see that you are using add_node or get_node anywhere, but I'm assuming you would when actually using this class.

Nevertheless, I think these functions would better be called __setitem__ and __getitem__, allowing usage, such as g = Graph(); g[5] = Node(5) and print g[5]. This would also make initializing the graph easier, which leads me to my next recommendation.

I would expect the Graph class to take an argument on initialization to directly build a graph (without having to manually add every single node). 

Lastly, get_node can be greatly simplified by using dict.get, which returns None when the key is not present in the dictionary.

class Graph:
    def __init__(self, nodes=None):
        self.nodes = dict()
        if nodes is not None:
            for _id in nodes:
                self[_id] = Node(_id)

    def __setitem__(self, _id, val):
        self.nodes[_id] = val

    def __getitem__(self, _id):
        return self.nodes.get(_id)

    def add_node(self, _id):
        self[_id] = Node(_id)

    ...


This allows initializing an instance like this: Graph([1,2,3]). It does not, however, allow initializing a nested structure.

Regarding your questions:


Use dict.get
I would maybe use _, cur_node = queue.get(0) to make it clearer that you don't need the priority here.
I think it is still quite readable.
deque does not seem too exotic to me, but then again, I don't perform job interviews, so who know.


Last but not least, I would have a look at whether you really need queue.PriorityQueue here. One of its features is that it is thread-safe, because it performs locking when adding or popping values from the queue. However, it also incurs a performance hit because of this (I saw a factor 2 being discussed for Python 2.6).

Instead you could roll your own implementation using heapq, similar to the one shown in the implementation details for heapq, maybe without the part about REMOVED entries, because you don't change the priority of a neighbour once you have calculated it. So you could use:

from heapq import heappush, heappop
import itertools

class PriorityQueue:
    def __init__(self, tasks=None):
        '''A new PriorityQueue.
        Parameters:
            tasks:    iterable of (priority, task) tuples'''
        self.pq = []                         # list of entries arranged in a heap
        self.counter = itertools.count()     # unique sequence count

        if tasks is not None:
            for priority, task in tasks:
                self.add_task(task, priority)

    def add_task(self, task, priority=0):
        'Add a new task'
        count = next(self.counter)
        entry = (priority, count, task)
        heappush(self.pq, entry)

    def pop_task(self):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        if self.pq:
            _, _, task = heappop(self.pq)
            return task
        raise KeyError('pop from an empty priority queue')


This should basically be how queue.PriorityQueue is implemented as well, but without the locking. Note that heapq is implemented in C, so it is quite fast. You would have to make some performance comparisons to see how this performs with respect to queue.PriorityQueue.