exploredit chooses the shortest path (assuming that there is onefrom the start to the goal the code is bit more complicated than the algorithm we just described because it has to deal with the possibility of the graph containing cycles it also avoids exploring paths longer than the shortest path that it has already found the function search calls dfs with path [(to indicate that the current path being explored is emptyand shortest none (to indicate that no path from start to end has yet been founddfs begins by choosing one child of start it then chooses one child of that node and so onuntil either it reaches the node end or node with no unvisited children the check if node not in path prevents the program from getting caught in cycle the check if shortest =none or len(pathlen(shortest)is used to decide if it is possible that continuing to search this path might yield shorter path than the best path found so far if sodfs is called recursively if it finds path to end that is no longer than the best found so farshortest is updated when the last node on path has no children left to visitthe program backtracks to the previously visited node and visits the next child of that node the function returns when all possibly shortest paths from start to end have been explored figure contains some code that runs the code in figure the function testsp in figure first builds directed graph like the one pictured on the rightand then searches for shortest path between node and node