This lesson's interactive features are locked, please to keep using them

Dijkstra's vs. DFS

We mentioned earlier that testing of the Mappy app showed that simpler search algorithms like BFS and DFS are too slow for finding optimal routes.

Let's prove that for ourselves! We'll use two algorithms to find the shortest path from a source to a destination in the same graph: one of them Dijkstra's, the other DFS-based. And we'll count how many nodes each has to visit in order to find that path.

To make things easier, nearly complete implementations of both algorithms are provided. You'll just need to add counting of node visits.

Function Arguments and Return Values

Both functions, dijkstra and dfs_path, take the same arguments and should have the same return types.

There are three arguments:

graph – An adjacency dictionary, i.e. a mapping of nodes to their direct destinations, also indicating the cost/distance of each link. For example, if the only direct destination from Austin is Miami, with a cost of 40, it will be represented as "Austin": {"Miami": 40}. The Python type of graph would be dict[str, dict[str, int]].
src – The source node (str).
dest – The destination node (str).

And the return should consist of two values:

The optimal path, as a list of strings.
The number of nodes visited by the algorithm. (This is what you'll need to add.)

Assignment

Add the code to count node visits in both the dijkstra and dfs_path functions. Here are suggested steps (the same for each function):

Toward the beginning of the function, initialize a counter for the number of nodes visited, starting at 0.
Increment the counter each time a new node is visited. You'll need to find the right place to do this.
Update the return value to include the number of node visits.

Once you have tests passing, look closely at the output. What do you notice?