when executedtestsp produces the output current dfs path current dfs path -> current dfs path -> -> current dfs path -> -> -> current dfs path -> -> -> -> current dfs path -> -> -> -> current dfs path -> -> -> current dfs path -> current dfs path -> -> current dfs path -> -> -> current dfs path -> -> -> current dfs path -> -> -> current dfs path -> -> shortest path found by dfs -> -> -> notice that after exploring the path -> -> -> -> it backs up to node and explores the path -> -> -> -> after saving that as the shortest successful path so farit backs up to node and explores the path -> -> -> when it reaches the end of that path (node )it backs up all the way to node and investigates the path starting with the edge from to and so on the dfs algorithm implemented above finds the path with the minimum number of edges if the edges have weightsit will not necessarily find the path that minimizes the sum of the weights of the edges howeverit is easily modified to do so of coursethere are other ways to traverse graph than depth-first another common approach is breadth-first search (bfsin breadth-first traversal one first visits all children of the start node if none of those is the end nodeone visits all children of each of those nodes and so on unlike depth-first searchwhich is usually implemented recursivelybreadth-first search is usually implemented iteratively bfs explores many paths simultaneouslyadding one node to each path on each iteration since it generates the paths in ascending order of lengththe first path found with the goal as its last node is guaranteed to have minimum number of edges figure contains code that uses breadth-first search to find the shortest path in directed graph the variable pathqueue is used to store all of the paths currently being explored each iteration starts by removing path from pathqueue and assigning that path to tmppath if the last node in tmppath is endtmppath is returned otherwisea set of new paths is createdeach of which extends tmppath by adding one of its children each of these new paths is then added to pathqueue