Algorithm of the Shortest Path Problem Objective of the nth iteration: Find the nth nearest node to the origin (to be repeated for n=1,2,..., until the nth nearest node is the destination). Input for the nth iteration: (n-1) nearest nodes to the origin, including their shortest path and distance from the origin (These nodes plus the origin are called solved nodes; others are unsolved nodes). Candidate for the nth nearest node: Each solved node that is directly connected by a link to one or more unsolved nodes provides one candidate, that is, the unsolved node with the shortest connecting link (ties provide additional candidates). Calculation of the nth nearest node: For each solved and its candidate add the distance between them and the distance of the shortest path from the origin to this selected node. The candidate with the smallest such total distance is the nth nearest node, and its shortest path is the one generating this distance.

You need to take a trip by car to another town that you have never visited before. Therefore, you are studying a map to determine the shortest route to your destination. Depending on which route you choose, there are five other towns (call them A, B, C, D, E) that you might pass through on the way. The map shows the mileage along each road that directly connects two towns without any intervening towns. These numbers are summarized in the following table, where a dash (-) indicates that there is no road directly connecting these two towns without going through any other towns. A B Destination Town Origin A 40 60 10 Miles between adjacent towns D E 50 70 20 55 40 50 10 B D E 60 80 (a) Formulate this problem as a shortest-path problem by drawing a network where nodes represent towns, links represent roads, and numbers indicate the length of each link in miles. (2 points) (b) Use the algorithm described during my lectures and documented on Word document, "Chapter 5 Supplement- Network theory.doc" (posted on the Canvas course page) to solve this shortest-path problem. (3 points) ) Formulate and solve a spreadsheet model for this problem. (5 points)