Explores all nodes at distance 1, then all nodes at distance 2, etc.

Because it goes with increasing distances, once a solution is found, we know it’s the shortest path.

Algorithm

Start at an initial node
Consider all the edges that leave that node, in some order
Follow the first edge, and check to see if at goal node
If not, try the next edge rom the current node
Continue until either find goal node, or run out of options
- When run out of edge options, move to next node at same distance from start, and repeat
- When run out of node options, move to next level in the graph (all nodes one step fruther from start) and repeat

Example code

def BFS(graph, start, end):
	initPath = [start]
	pathQueue = [initPath]
	while len(pathQueue) != 0:
		tmpPath = pathQueue.pop(0)
		lastNode = tmpPath[-1]
 
	if lastNode == end:
		return tmpPath
 
	for nextNode in graph.childrenOf(lastNode):
		if nextNode not in tmpPath:
			newPath = tmpPath + [nextNode]
			pathQueue.append(newPath)