graph algorithms / / / / / / / / / / / / / / / / / / figure earliest completion timelatest completion timeand slack figure shows the slack (as the third entryfor each activity in the event-node graph for each nodethe top number is the earliest completion time and the bottom entry is the latest completion time some activities have zero slack these are critical activitieswhich must finish on schedule there is at least one path consisting entirely of zero-slack edgessuch path is critical path all-pairs shortest path sometimes it is important to find the shortest paths between all pairs of vertices in the graph although we could just run the appropriate single-source algorithm |vtimeswe might expect somewhat faster solutionespecially on dense graphif we compute all the information at once in we will see an (| | algorithm to solve this problem for weighted graphs althoughfor dense graphsthis is the same bound as running simple (nonpriority queuedijkstra' algorithm |vtimesthe loops are so tight that the specialized all-pairs algorithm is likely to be faster in practice on sparse graphsof courseit is faster to run |vdijkstra' algorithms coded with priority queues shortest path example in this section we write some +routines to compute word ladders in word ladder each word is formed by changing one character in the ladder' previous word for instancewe can convert zero to five by sequence of one-character substitutions as followszero hero here hire fire five this is an unweighted shortest problem in which each word is vertexand two vertices have edges (in both directionsbetween them if they can be converted to each other with one-character substitution in section we described and wrote +routine that would create map in which the keys are wordsand the values are vectors containing the words that can result from one-character transformation as suchthis map represents the graphin adjacency list formatand we only need to write one routine to run the single-source unweighted shortest-path algorithm and second routine to output the sequence of wordsafter the