listing continued thegraph addedge( )/bc thegraph addedge( )/bd thegraph addedge( )/be thegraph addedge( )/cd thegraph addedge( )/ce thegraph addedge( )/cf thegraph addedge( )/de thegraph addedge( )/ef system out print("minimum spanning tree")thegraph mstw()/minimum spanning tree system out println()/end main(/end class mstwapp //////////////////////////////////////////////////////////////the main(routine in class mstwapp creates the tree in figure here' the outputminimum spanning treead ab be ec cf the shortest-path problem perhaps the most commonly encountered problem associated with weighted graphs is 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 preceding 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 isthe fare from 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 fares