weighted graphs building the ajo-bordo link after you've completed the ajo-danza link and built your office in danzayou can send out surveyors from danza to all the towns reachable from there these are bordocolinaand erizo the surveyors reach their destinations and report back costs of and million dollarsrespectively (of courseyou don' send surveyor to ajo because you've already surveyed the ajo-danza route and installed its cable now you know the costs of four links from towns with offices to towns with no officesajo-bordo$ million danza-bordo$ million danza-colina$ million danza-erizo$ million why isn' the ajo-danza link still on the listbecause you've already installed the cable therethere' no point giving any further consideration to this link the route on which cable has just been installed is always removed from the list at this point it may not be obvious what to do next there are many potential links to choose from what do you imagine is the best strategy nowhere' the rulerule from the listalways pick the cheapest edge actuallyyou already followed this rule when you chose which route to follow from ajothe ajo-danza edge was the cheapest here the cheapest edge is ajo-bordoso you install cable link from ajo to bordo for cost of million dollarsand build an office in bordo let' pause for moment and make general observation at given time in the cable system constructionthere are three kinds of towns towns that have offices and are linked by cable (in graph terms they're in the minimum spanning tree towns that aren' linked yet and have no officebut for which you know the cost to link them to at least one town with an office we can call these "fringetowns towns you don' know anything about