Until the preceding chapter, we explored only the simple ways of graph traversal, Breadth First Search (BFS) and Depth First Search (DFS). We did discuss in brief in the preceding chapter about Dijkstra and how it can help us determine the path from node A to node B in a graph, provided the graph is directed with weighted edges.

In this example, we have just that. We have a graph of nodes (cities) and edges (approximate distance in miles), and we need to determine the fastest path for a user to reach a destination node from a given start node, provided other factors, such as speed, traffic, and weather, remain constant:

Our trip starts from San Francisco (SF) and ends in Phoenix (PX). We have identified some intermediate cities in which the user can stop for rest or gas: Monterey (MT), San Jose (SJ), Santa Barbara (SB), Los Angeles (LA), San Diego (SD), Fresno (FR), Bakersfield (BK), and Las Vegas (LV). The distance to each of these cities is indicated by the weights that are associated with each of the edges between the cities.