Depth-first search (DFS) follows one branch of a tree as far as it can, then backtracks to explore another. In delivery routing, each branch represents a sequence of customer stops; DFS can compare completed routes by their accumulated cost. section 7.2 section 7.5
A recursive route search follows this pattern:
- Extend the current route with an unvisited customer and add the travel cost. section 7.2
- When the route is complete, compare its cost with the best found so far; otherwise, keep exploring and backtrack to try another branch. section 7.2
Listing 7.6. DFS algorithm implementation.
best_route = None
best_cost = float('inf')
def dfs(node):
global best_route, best_cost
if len(node.route) == len(NODES): #A
if node.cost < best_cost: #A
best_cost = node.cost. #A
best_route = node.route #A
return
for customer in NODES:
if customer not in node.route:
next_cost = node.cost +
➥distances[(node.route[-1], customer)] #B
child = RouteNode(route=node.route
➥+ [customer], cost=next_cost) #B
node.add_child(child) #B
dfs(child) #C
root = RouteNode(route=["Depot"], cost=0)
dfs(root)
See a recursive DFS implementation that builds customer routes and tracks the lowest-cost complete route. section 7.2
DFS uses less memory than breadth-first search, but does not guarantee the shortest path. Exhaustively exploring routes also becomes impractical as the number of customers grows. section 7.5








