cost but shorter path exists by following the loop which has cost - this path is still not the shortestbecause we could stay in the loop arbitrarily long thusthe shortest path between these two points is undefined similarlythe shortest path from to is undefinedbecause we can get into the same loop this loop is known as negative-cost cyclewhen one is present in the graphthe shortest paths are not defined negative-cost edges are not necessarily badas the cycles arebut their presence seems to make the problem harder for conveniencein the absence of negative-cost cyclethe shortest path from to is zero there are many examples where we might want to solve the shortest-path problem if the vertices represent computersthe edges represent link between computersand the costs represent communication costs (phone bill per megabyte of data)delay costs (number of seconds required to transmit megabyte)or combination of these and other factorsthen we can use the shortest-path algorithm to find the cheapest way to send electronic news from one computer to set of other computers we can model airplane or other mass transit routes by graphs and use shortestpath algorithm to compute the best route between two points in this and many practical applicationswe might want to find the shortest path from one vertexsto only one other vertext currently there are no algorithms in which finding the path from to one vertex is any faster (by more than constant factorthan finding the path from to all vertices we will examine algorithms to solve four versions of this problem firstwe will consider the unweighted shortest-path problem and show how to solve it in (| |+| |nextwe will show how to solve the weighted shortest-path problem if we assume that there are no negative edges the running time for this algorithm is (|elog | |when implemented with reasonable data structures if the graph has negative edgeswe will provide simple solutionwhich unfortunately has poor time bound of (| | |finallywe will solve the weighted problem for the special case of acyclic graphs in linear time unweighted shortest paths figure shows an unweighted graphg using some vertexswhich is an input parameterwe would like to find the shortest path from to all other vertices we are only interested in the number of edges contained on the pathso there are no weights on the edges this is clearly special case of the weighted shortest-path problemsince we could assign all edges weight of for nowsuppose we are interested only in the length of the shortest pathsnot in the actual paths themselves keeping track of the actual paths will turn out to be matter of simple bookkeeping suppose we choose to be immediatelywe can tell that the shortest path from to is then path of length we can mark this informationobtaining the graph in figure now we can start looking for all vertices that are distance away from these can be found by looking at the vertices that are adjacent to if we do thiswe see that and are one edge from this is shown in figure we can now find vertices whose shortest path from is exactly by finding all the vertices adjacent to and (the vertices at distance )whose shortest paths are not