Performance of BFS in Python 3

How can I increase speed performance of this Python 3 programming challenge?


Find the shortest path from one point to another (last line)


Example:

4 4
1 2
4 1
2 3
3 1
2 4

Output:

2

Explanation:

4--3  
| /|  
|/ |  
1--2

The shortest path: 2-1-4

import sys
from queue import Queue

def bfs(graph, start, end):
    global distance
    # path var for store current path
    path = ()
    Q = Queue()
    Q.put(start)
    # visited dict, store key - visited vertices, value - path from the start
    # query - to store current queue items
    while Q.empty() is False:
        # take last element from the queue
        u = Q.get()
        path = path + (u,)
        # set it to visited and add current path
        if u == end:
            return distance[end]
        # go trough its children
        for child in graph[u]:
            if distance[child] == 0:
                # add it to queue
                Q.put(child)
                distance[child] = distance[u] + 1
    else:
        return -1

if __name__ == '__main__':
    global distance
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    adj = [[] for _ in range(n)]
    distance = [0 for _ in range(n)]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    edges.sort()
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    s, t = data[2 * m] - 1, data[2 * m + 1] - 1
    print(bfs(adj, s, t))

This code must build a graph adjacency list in format [[1][0,2][1], where list index is graph node index, and numbers are connected edges to it.

The input format is next:

3 2
1 2
2 3

where the first two numbers is the number of vertexes (3) and number of edges (2), and the next lines describe the connections through graph vertices.

1. Review

-
The bfs function relies on a global variable distance. This make it hard to test (you have to remember to set up the distance list before you call bfs) and means that it can't be used from multiple threads. It would be better if bfs constructed all its own data structures.

-
The path variable is a tuple of all the vertices that have been visited so far. Adding a new element to the path, as in path = path + (u,), requires copying out the old path. This makes the overall runtime \$\Omega(n^2)\$. But path is not actually used for anything, so you could just remove it.

-
queue.Queue is a thread-safe data structure intended for use by multi-threaded programs. It has to take and release a lock for every operation, so it is overkill to use this in a single-threaded program. It is more than ten times faster to use collections.deque instead.

-
The code handles the exceptional situation (no path is found) by returning an exceptional value (−1). This is an error-prone design because it would be very easy for the caller to forget to check for the exceptional value. It would be easy to write code like this:

dist = bfs(graph, start, end)
if dist <= goal:
    print("reachable in {} steps or fewer".format(goal))

which would go wrong when dist is -1. It's better to handle an exceptional situation by raising an exception.

-
The code checks to see whether a vertex is equal to end after removing it from the queue. But it would be better to do this check before adding a vertex to the queue — that way you wouldn't have to wait for the vertex to move all the way up the queue before you spot that the search is done.

This optimization works for this problem because all the edges have the same length and so breadth-first search adds vertices to the queue in order by their distance from the start. This means that as soon as you've found a path to end you know that more searching cannot find a shorter path.

-
The value distance[u] + 1 is computed again for every child. It would be better to compute it once and remember it.

1. Revised code

from collections import deque

class NotFound(Exception):
    """Exception raised when no path is found."""

def bfs(graph, start, end):
    """Return the shortest distance from start to end in graph, which is
    represented as a mapping from a vertex to a list of adjacent
    vertices. If there is no path from start to end, raise NotFound.
    """
    # Mapping from v to shortest distance from start to v.
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        d = distance[u] + 1
        for neighbour in graph[u]:
            if neighbour not in distance:
                if neighbour == end:
                    return d
                distance[neighbour] = d
                queue.append(neighbour)
    else:
        raise NotFound()

StackExchange Code Review Q#162011, answer score: 4