dijkstra' algorithm the solution we'll show for the shortest-path problem is called dijkstra' algorithmafter edsger dijkstrawho first described it in this algorithm is based on the adjacency matrix representation of graph somewhat surprisinglyit finds not only the shortest path from one specified vertex to anotherbut also the shortest paths from the specified vertex to all the other vertices agents and train rides to see how dijkstra' algorithm worksimagine that you want to find the cheapest way to travel from ajo to all the other towns in magnaguena you (and various agents you will hireare going to play the role of the computer program carrying out dijkstra' algorithm of coursein real life you could probably obtain schedule from the railroad with all the fares the algorithmhowevermust look at one piece of information at timeso (as in the preceding sectionwe'll assume that you are similarly unable to see the big picture at each townthe stationmaster can tell you how much it will cost to travel to the other towns that you can reach directly (that isin single ridewithout passing through another townalashe cannot tell you the fares to towns further than one ride away you keep notebookwith column for each town you hope to end up with each column showing the cheapest route from your starting point to that town the first agentin ajo eventuallyyou're going to place an agent in every townthis agent' job is to obtain information about ticket costs to other towns you yourself are the agent in ajo all the stationmaster in ajo can tell you is that it will cost $ to ride to bordo and $ to ride to danza you write this information in your notebookas shown in table table step an agent at ajo from ajo tobordo colina danza erizo step (via ajoinf (via ajoinf the entry "infis short for "infinity,and means that you can' get from ajo to the town shown in the column heador at least that you don' yet know how to get there (in the algorithm infinity will be represented by very large numberwhich will help with calculationsas we'll see the table entries in parentheses show the last town visited before you arrive at the various destinations we'll see later why this is good to know what do you do nowhere' the rule you'll followrule always send an agent to the town whose overall fare from the starting point (ajois the cheapest