table step agents at ajo and bordo from ajo tobordo colina danza erizo step step (via ajo (via ajo)inf (via bordo (via ajo (via ajoinf inf after we've installed an agent in townwe can be sure that the route taken by the agent to get to that town is the cheapest route whyconsider the present case if there were cheaper route than the direct one from ajo to bordoit would need to go through some other town but the only other way out of ajo is to danzaand that ride is already more expensive than the direct route to bordo adding additional fares to get from danza to bordo would make the danza route still more expensive from this we decide that from now on we won' need to update the entry for the cheapest fare from ajo to bordo this fare will not changeno matter what we find out about other towns we'll put next to it to show that there' an agent in the town and that the cheapest fare to it is fixed three kinds of towns as in the minimum spanning tree algorithmwe're dividing the towns into three categories towns in which we've installed an agentthey're in the tree towns with known fares from towns with an agentthey're on the fringe unknown towns at this point ajo and bordo are category towns because they have agents there category towns form tree consisting of paths that all begin at the starting vertex and that each end on different destination vertex (this is not the same treeof courseas minimum spanning tree some other towns have no agentsbut you know the fares to them because you have agents in adjacent category towns you know the fare from ajo to danza is $ and from bordo to colina is $ because the fares to them are knowndanza and colina are category (fringetowns you don' know anything yet about erizoit' an "unknowntown figure shows these categories at the current point in the algorithm as in the minimum spanning tree algorithmthis algorithm moves towns from the unknown category to the fringe categoryand from the fringe category to the treeas it goes along