graph algorithms void graph::unweightedvertex queue qfor each vertex dist infinitys dist enqueues )while! isemptyvertex dequeue)for each vertex adjacent to ifw dist =infinity dist dist path vq enqueuew )figure psuedocode for unweighted shortest-path algorithm we keep all of the same information as before thuseach vertex is marked as either known or unknown tentative distance dv is kept for each vertexas before this distance turns out to be the shortest path length from to using only known vertices as intermediates as beforewe record pv which is the last vertex to cause change to dv the general method to solve the single-source shortest-path problem is known as dijkstra' algorithm this thirty-year-old solution is prime example of greedy algorithm greedy algorithms generally solve problem in stages by doing what appears to be the best thing at each stage for exampleto make change in currencymost people count out the quarters firstthen the dimesnickelsand pennies this greedy algorithm gives change using the minimum number of coins the main problem with greedy algorithms is that they do not always work the addition of -cent piece breaks the coin-changing algorithm for returning centsbecause the answer it gives (one -cent piece and three penniesis not optimal (one dime and one nickeldijkstra' algorithm proceeds in stagesjust like the unweighted shortest-path algorithm at each stagedijkstra' algorithm selects vertexvwhich has the smallest dv among all the unknown vertices and declares that the shortest path from to is known the remainder of stage consists of updating the values of dw in the unweighted casewe set dw dv if dw thuswe essentially lowered the value of dw if vertex offered shorter path if we apply the same logic to the weighted