I have the following code which computes the BFS of paths. I know that regular BFS is O(|V| +|E|) because the outer loop runs O(|V|) times, as we visit each vertex once, and the inner loop for visiting each adjacent neighbour of a vertex will run at most O(|E|), since we traverse each edge once (or twice if its undirected), giving a total time complexity of O(|V| + |E|) (or just O(|V|)).

For the code below, I am doing a BFS of paths. The algorithm is largely the same except that each time we come across a unvisited vertex, I make a copy of the path, add the new vertex to the path then append it to the queue of paths.

I am wondering what the worst case time/space complexity is.

My initial guess is that the time complexity is O(|V|^2 * |E|). As before, the outer loop runs at most O(|V|) times, as we visit each vertex once, the inner loop runs at most O(|E|) times as we visit each edge once (or twice if undirected). However, in the worse case the graph could be a line of |V| vertices, where within the inner loop we may do a copy of 1 item the first time, 2 the second time, ..., V the last time. This would mean the inner loop across O(|E|) iterations, copies 1 + 2 + ... + V = V(V+1)/2 items.

Does this mean the overall time complexity is O(|V| + |V|^2 * |E|) = O(|V|^2 * |E|) ?

The space complexity I believe is O(db^d), where d is the depth from source node, b is branching factor.

def bfsPaths(src, dest):
	visited = set()
	queue = []

	queue.append([src])
	visited.add(src)

	while queue:
		v = queue.pop(0)

		if v[-1] == dest:
			return v

		for n in graph[v[-1]]:
			if n not in visited:
				new_path = list(v)
				new_path.append(n)
				queue.append(new_path)
				visited.add(n)