weighted graphs bordo colina $ $ $ ajo $ $ $ $ danza figure $ erizo train fares in magnaguena the edges in figure are directed they represent single-track railroad lineson which (in the interest of safetytravel is permitted in only one direction for exampleyou can go directly from ajo to bordobut not from bordo to ajo although in this situation we're interested in the cheapest faresthe graph problem is nevertheless always referred to as the shortest-path problem (spphere shortest doesn' necessarily mean shortest in terms of distanceit can also mean cheapestfastestor best route by some other measure cheapest fares there are several possible routes between any two towns for exampleto take the train from ajo to erizoyou could go through danzaor you could go through bordo and colinaor through danza and colinaor you could take several other routes (it' not possible to reach the town of flor by rail because it lies beyond the rugged sierra descaro rangeso it doesn' appear on the graph this is fortunatebecause it reduces the size of certain lists we'll need to make the shortest-path problem is thisfor given starting point and destinationwhat' the cheapest routein figure you can see (with little mental effortthat the cheapest route from ajo to erizo passes through danza and colinait will cost you $ directedweighted graph as we notedour railroad has only single-track linesso you can go in only one direction between any two cities this corresponds to directed graph we could have portrayed the more realistic situation in which you can go either way between two cities for the same pricethis would correspond to non-directed graph howeverthe shortest-path problem is similar in these casesso for variety we'll show how it looks in directed graph