graph algorithms single-source shortest-path algorithm has completed these two routines are both shown in figure the first routine is findchainwhich takes the map representing the adjacency lists and the two words to be connected and returns map in which the keys are wordsand the corresponding value is the word prior to the key on the shortest ladder starting at first in other wordsin the example aboveif the starting word is zerothe value for key five is firethe value for key fire is hirethe value for key hire is hereand so on clearly this provides enough information for the second routinegetchainfrompreviousmapwhich can work its way backward findchain is direct implementation of the pseudocode in figure and for simplicityit assumes that first is key in adjacentwords (this is easily tested prior to the callor we can add extra code at line that throws an exception if this condition is not satisfiedthe basic loop incorrectly assigns previous entry for first (when the initial word adjacent to first is processedso at line that entry is repaired getchainfromprevmap uses the prev map and secondwhich presumably is key in the map and returns the words used to form the word ladder by working its way backward through prev this generates the words backwardso the stl reverse algorithm is used to fix the problem the cast at line is needed because operator[cannot be applied on an immutable map it is possible to generalize this problem to allow single-character substitutions that include the deletion of character or the addition of character to compute the adjacency list requires only little more effortin the last algorithm in section every time representative for word in group is computedwe check if the representative is word in group if it isthen the representative is adjacent to (it is single-character deletion)and is adjacent to the representative (it is single-character additionit is also possible to assign cost to character deletion or insertion (that is higher than simple substitution)and this yields weighted shortest-path problem that can be solved with dijkstra' algorithm network flow problems suppose we are given directed graph (vewith edge capacities cv, these capacities could represent the amount of water that could flow through pipe or the amount of traffic that could flow on street between two intersections we have two verticesswhich we call the sourceand twhich is the sink through any edge(vw)at most cv, units of "flowmay pass at any vertexvthat is not either or tthe total flow coming in must equal the total flow going out the maximum-flow problem is to determine the maximum amount of flow that can pass from to as an examplefor the graph in figure on the left the maximum flow is as indicated by the graph on the right although this example graph is acyclicthis is not requirementour (eventualalgorithm will work even if the graph has cycle as required by the problem statementno edge carries more flow than its capacity vertex has three units of flow coming inwhich it distributes to and vertex takes three units of flow from and and combines thissending the result to vertex can