knapscak and graph optimization problems some metriclocal choice at each step it makes choice that is locally optimal howeveras this example illustratesa series of locally optimal decisions does not always lead to solution that is globally optimal despite the fact that they do not always find the best solutiongreedy algorithms are often used in practice they are usually easier to implement and more efficient to run than algorithms guaranteed to find optimal solutions as ivan boesky once said" think greed is healthy you can be greedy and still feel good about yourself there is variant of the knapsack problemcalled the fractional (or continuousknapsack problemfor which greedy algorithm is guaranteed to find an optimal solution since the items are infinitely divisibleit always makes sense to take as much as possible of the item with the highest remaining valueto-weight ratio supposefor examplethat our burglar found only three things of value in the housea sack of gold dusta sack of silver dustand sack of raisins in this casea greedy-by-density algorithm will always find the optimal solution graph optimization problems let' think about another kind of optimization problem suppose you had list of the prices of all of the airline flights between each pair of cities in the united states suppose also that for all citiesaband cthe cost of flying from to by way of was the cost of flying from to plus the cost of flying from to few questions you might like to ask arewhat is the smallest number of stops between some pair of citieswhat is the least expensive airfare between some pair of citieswhat is the least expensive airfare between some pair of cities involving no more than two stopswhat is the least expensive way to visit some collection of citiesall of these problems (and many otherscan be easily formalized as graph problems graph is set of objects called nodes (or verticesconnected by set of edges (or arcsif the edges are unidirectional the graph is called directed graph or digraph in directed graphif there is an edge from to we refer to as the source or parent node and as the destination or child node he said thisto enthusiastic applausein commencement address at the university of california at berkeley business school few months later he was indicted for insider tradinga charge that led to two years in prison and $ , , fine computer scientists and mathematicians use the word "graphin the sense used in this book they typically use the word "plotto denote the kind of graphs we saw in -