• Start off with 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, repeat the process from new node
  • Continue until either find goal node, or run out of options
    • When run out of options, backtrack to the previous node and try the next edge, repeating this process

Example code

def DS(graph, start, end, path, shortest):
	path = path + [start]
	if start == end:
		return path
	for node in graph.childrenOf(start):
		if node not in path: # avoid cycles
			if shortest == None or len(path) < len(shortest):
				newPath = DFS(graoh, node, end, path, shortest)
				if newPath != None
					shortest = newPath
	return shortest
def shortestPath(graph, start, end):
	return DFS(graph, start, end, [], None)