Sorry I don't know Python at all but I looked at your code as hard as I can and it all looks fine to me. It's almost identical to what I did in Java, but for what it's worth I'll also explain my solution: I have only one priority queue where a node's priority is defined as it's distance from S. Each node also has a "visited" field. You start with S.distance = 0 and all other nodes have a distance infinity, and all visited fields are false. In the beginning, the queue has only S. While the queue still has nodes: You remove a node P from the queue, and mark it visited. For every child C of P that hasn't been visited before, you set C.distance = P.distance + 1, and insert C in the queue. And so on. In the end, I print all distance fields.