complete graph prior to the search, requiring the BFS to expand the nodes
as it explores, a search could take literally years to terminate. In their book
Artificial Intelligence: A Modern Approach, Russell and Norvig give an
example of a puzzle with a branching factor of 10; assuming that it takes
one millisecond to expand each node, the BFS will take 3,500 years to
reach a depth of 14! Computers have become much faster beasts since the
first edition of that book was published, but even so you would still be an
old man in the amount of time the BFS takes to get to this depth.
Cost-Based Graph Searches
For many problem domains, the related graph will have a cost (sometimes
referred to as a weight) associated with traversing an edge. For instance,
navigation graphs usually have edges with a cost proportional to the dis
tance between the nodes they connect. To find the shortest paths through
the graph these costs must be taken into account. It’s simply not enough —
as we did previously with the BFS — to find the path containing the fewest
number of edges because, with an associated cost, it can be much cheaper
to travel down many short edges than two long ones. See Figure 5.30.
Although it’s possible to use the BFS or DFS to exhaustively search
through all the routes to a target node, adding up the costs of each path as it
goes and then selecting the lowest cost path, it’s obviously a very ineffi
cient solution. Fortunately there are much better methods at our disposal.
The search algorithms discussed in the remainder of this chapter are based
on a technique called edge relaxation. As an algorithm proceeds it gathers
information about the best path found so far (BPSF) from the source node
to any of the other nodes en route to the target. This information is updated
The Secret Life of Graphs | 231
Graph Search Algorithms
Figure 5.30. The path1-5-4-3isshorter than the path1-2-3even though it
contains more edges.