minimum length path (also called shortest pathfrom to uif such path exists people often use the convention that (vuif there is no path at all from to in even if there is path from to in gthe distance from to may not be definedhoweverif there is cycle in whose total weight is negative for examplesuppose vertices in represent citiesand the weights of edges in represent how much money it costs to go from one city to another if someone were willing to actually pay us to go from say jfk to ordthen the "costof the edge (jfk,ordwould be negative if someone else were willing to pay us to go from ord to jfkthen there would be negative-weight cycle in and distances would no longer be defined that isanyone could now build path (with cyclesin from any city to another city that first goes to jfk and then cycles as many times as he or she likes from jfk to ord and backbefore going on to the existence of such paths would allow us to build arbitrarily low negative-cost paths (andin this casemake fortune in the processbut distances cannot be arbitrarily low negative numbers thusany time we use edge weights to represent distanceswe must be careful not to introduce any negative-weight cycles suppose we are given weighted graph gand we are asked to find shortest path from some vertex to each other vertex in gviewing the weights on the edges as distances in this sectionwe explore efficient ways of finding all such shortest pathsif they exist the first algorithm we discuss is for the simpleyet commoncase when all the edge weights in are nonnegative (that isw( > for each edge of )hencewe know in advance that there are no negative-weight cycles in recall that the special case of computing shortest path when all weights are equal to one was solved with the bfs traversal algorithm presented in section there is an interesting approach for solving this single-source problem based on the greedy method design pattern (section recall that in this pattern we solve the problem at hand by repeatedly selecting the best choice from among those available in each iteration this paradigm can often be used in situations where we are trying to optimize some cost function over collection of objects we can add objects to our collectionone at timealways picking the next one that optimizes the function from among those yet to be chosen dijkstra' algorithm the main idea in applying the greedy method pattern to the single-source shortestpath problem is to perform "weightedbreadth-first search starting at in particularwe can use the greedy method to develop an algorithm that iteratively grows "cloudof vertices out of vwith the vertices entering the cloud in order of