Optimizing Python BFS Code

Question

g = input().split() N, M = int(g[0]), int(g[1]) high = 2 ** 32 - 1 map = [[(high) for i in range(N)] for i in range(N)] for i in range(M): g = input().split() left, right, value = int(g[0])-1, int(g[1])-1, int(g[2]) map[left][right] = min(value, map[left][right]) map[right][left] = min(value, map[right][left]) # END INPUT queue = [0] costs = [(high) for i in range(N)] costs[0] = 0 #camefrom = [-1 for i in range(N)] while len(queue) > 0: current = queue.pop() cost = costs[current] for i in range(N): #if i == current: # continue if costs[current] >= costs[i]: continue g = cost + map[current][i] if g < costs[i]: queue.append(i) costs[i] = g print('\n'.join([("-1" if i == high else str(i)) for i in costs])) 

While trying to translate my Java solution (that did work) to Python for this problem I've realized that it keeps reaching the time limit. Otherwise, it works perfectly fine, getting maybe half the answers right. I've looked at other answers and I just can't figure out how their code is so much more efficient than mine.

Any ideas for optimization?

Answer 1

current = queue.pop() 

What this actually does, which perhaps you did not notice, is remove the last element of the list. So the queue is really a stack, and instead of BFS this algorithm is really DFS. To make the queue work as a queue, you can use pop(0).

That makes a difference: DFS is more likely to do unnecessary redundant work in this scenario. Consider some node near the start. It has just been discovered with some suboptimal distance. DFS then immediately dives into all its neighbours and so on and updates all of them with suboptimal distances as well, which means that they'll get put on the queue (stack, really) again and again every time that they're updated with some new-but-still-suboptimal cost.

Answer 2

I have only a couple of nitpicks:

Nitpick 1

while len(queue) > 0: 

You can write just as:

while queue: 

Nitpick 2

Instead of a (list) queue, you need a deque:

from collections import deque 

This stems from the fact that list's pop(0) (as in @harold's answer) runs in \$\Theta(n)\$ time; with a deque you can do the same in \$\mathcal{O}(1)\$ (try it).