#### Analysis

Before proving the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, as we saw in Aggregate analysis. After initialization, no vertex is ever whitened, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O(V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of BFS is O(V E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G.

#### Shortest paths

At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G = (V, E) from a given source vertex s V. Define the shortest-path distance δ(s, v) from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s, v) = . A path of length δ(s, v) from s to v is said to be a shortest path from s to v. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances.