graph algorithms known dv pv figure after is declared known known dv pv figure after is declared known and algorithm terminates the path can be printed out using the recursive routine in figure the routine recursively prints the path all the way up to the vertex before on the pathand then just prints this works because the path is simple figure shows the main algorithmwhich is just for loop to fill up the table using the greedy selection rule proof by contradiction will show that this algorithm always works as long as no edge has negative cost if any edge has negative costthe algorithm could produce the wrong answer (see exercise ( )the running time depends on how the vertices are manipulatedwhich we have yet to consider if we use the obvious algorithm of sequentially scanning the vertices to find the minimum dv each phase will take (| |time to find the minimumand thus (| | time will be spent finding the minimum over the course of the algorithm the time for updating dw is constant per updateand there is at most one update per edge for total of (| |thusthe total running time is (| | | (| | if the graph is densewith | (| | )this algorithm is not only simple but also essentially optimalsince it runs in time linear in the number of edges if the graph is sparsewith | (| |)this algorithm is too slow in this casethe distances would need to be kept in priority queue there are actually two ways to do thisboth are similar