figure graph after finding all vertices whose shortest path is already known this search tells us that the shortest path to and is figure shows the progress that has been made so far finally we can findby examining vertices adjacent to the recently evaluated and that and have shortest path of three edges all vertices have now been calculatedand so figure shows the final result of the algorithm this strategy for searching graph is known as breadth-first search it operates by processing vertices in layersthe vertices closest to the start are evaluated firstand the most distant vertices are evaluated last this is much the same as level-order traversal for trees given this strategywe must translate it into code figure shows the initial configuration of the table that our algorithm will use to keep track of its progress for each vertexwe will keep track of three pieces of information firstwe will keep its distance from in the entry dv initially all vertices are unreachable except for swhose path length is the entry in pv is the bookkeeping variablewhich will allow us to print the actual paths the entry known is set to true after vertex is processed initiallyall entries are not knownincluding the start vertex when vertex is marked knownwe have figure final shortest paths