A shortest-path problem asks for the route between two locations or nodes that uses the fewest steps. A familiar example is finding the quickest route from Twin Peaks to the Golden Gate Bridge: check every one-step route, then every two-step route, until the destination appears. The first route found at the shallowest level is the shortest. section 6.1
Solve a shortest-path problem in two stages:
- Model the situation as a graph, with locations or people as nodes and their connections as edges. section 6.1
- Run breadth-first search, checking all nodes one step away before nodes two steps away, then three steps away. section 6.4
- Keep the search list in a queue so nodes are checked in the order they were added; otherwise, a longer route might be returned first. section 6.4
Finding the closest mango seller
Treat your social network as a graph. Search your first-degree friends before your second-degree connections. If no friend sells mangoes, add their friends to the queue and continue. The first seller found is the closest one by connection steps, because breadth-first search radiates outward from you. section 6.3 section 6.4
Use the route illustration to follow how candidate paths expand one step at a time until the destination is reached. section 6.1
