that of finding the shortest path between two given vertices the solution to this problem is applicable to wide variety of real-world situationsfrom the layout of printed circuit boards to project scheduling it is more complex problem than we've seen beforeso let' start by looking at (somewhatreal-world scenario in the same mythical country of magnaguena introduced in the last section the railroad line this time we're concerned with railroads rather than cable tv howeverthis project is not as ambitious as the last one we're not going to build the railroadit already exists we just want to find the cheapest route from one city to another the railroad charges passengers fixed fare to travel between any two towns these fares are shown in figure that isfrom ajo to bordo is $ from bordo to danza is $ and so on these rates are the same whether the ride between two towns is part of longer itinerary or not (unlike the situation with today' airline faresthe 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 figure train fares in magnaguena although in this situation we're interested in the cheapest faresthe graph problem is nevertheless always referred to as the shortest path problem here 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 erizo you 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 isfor 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 nondirected graph howeverthe