5
\$\begingroup\$
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?

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$
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.

\$\endgroup\$
1
  • \$\begingroup\$ With your change, my code now passes all the test cases. Thanks. \$\endgroup\$ Commented Jan 13, 2023 at 0:58
9
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.