Navigation: finding the shortest path/route

Objectives

• understand the problem of finding the shortest path/route
• develop an algorithm for the subproblem of retrieving the path between two locations
• implement the algorithm in a language
• practice implementation with loops and arrays

Prerequisites

• arrays, loops
• trees

Reading

• Background:

Materials

• Sample input data file florida10.txt
• Program: Map.java, ShortestPath.java with retrieving and printing the shortest route not completely defined (sample solution--complete program)

Activities

• On mapquest.com (or a similar website) find a route from the school to the White House (or other origin and destination)
• Ask them approximately how long it took (sub-second, seconds, minutes...)
• Ask if they were given paper maps, origin, and destination, how long would they take to find a (the shortest) route?
• Discuss there could be multiple levels of details (or abstraction):
  • country level (cities connected by highways),
  • city level (intersections connected by streets)
• Discuss if having only one level of abstraction (just interections connected by streets for the entire country) is a good idea? (Having two levels of abstraction helps us eliminate unnecessary details at the country level since we usually use highways, not small streets, between cities and speed up the computation)
• Let's focus on the country level: given origin city, destination city, and highway maps, find the shortest route.
• Form small groups of 3-4 students and ask each group to come up with ideas for solving the problem.
• This can be formulated into a "graph" problem:
  • nodes/vertices: cities
  • edges/links: highways connecting cities
  • weights/values of edges: length of highways
  • find the shorthest route from the origin node to the destination node
• Discuss the "shortest path" algorithm with visualization using a tree
  1. set up an array called shortestDistance, which stores the shortest distance to each city so far--initially unknown (or very large value).
  2. set up an array called visited, which stores if we have visited a particular city--initially all cities have not been visited.
  3. start from the origin city, called city1, and mark true in visited[city1]
  4. repeat the following if city1 is not the destination city:
     1. find all the neighboring cities that have not been visited
     2. for each of these neighboring cities (city2):
        1. calculate the total distance from the origin to city2
        2. update shortestDistance[city2] if the total distance is shorter than shortestDistance[city2]
     3. update city1 to be the city that has the smallest shortestDistance, but has not been visited
     4. update visited[city1] to be true
  5. we reached the destination city!
• Note that the above algorithm can tell the shortest total distance from shortestDistance[destinationCity], but not the sequence of intermediate cities on the shortest route
• Discuss how the path can be remembered
  • remember where you came from so that one can retrace the path back to the origin (ie, find destination's parent, grandparent, ... up to the root in the tree)
  • considered an array called previousLocation
  • for example, if city X is followed by city Y (X -> Y), previousLocation[Y] is X.
  • where in the algorithm do we want to update previousLocation? (when shortestDistance is updated in Step 4.2.2 because we only update shortestDistance when there is a shorter route)
  • how to udpate previousLocation? (add Step 4.2.3: previousLocation[city2] is city1)
• Given previousLocation, how to print the route in the normal direction? (trace backwards from destination to origin, store the cities in an array, print the array backwards)
• Ask them to implement tracing the route backwards and printing the route in the normal direction.
• Using different input values, check if their output matches the output from the sample solution.

Assessment

• Can the same algorithm be used for finding the shortest path at the city level? (yes)
• What are the vertices/nodes and edges/links in the graph at the city level? (nodes are intersections, links are streets)
• Can the algorithm be modified to find the shortest distance from the origin city to all other cities? (yes)
  • How can the algorithm be modified? (Step 4: Repeat until all cities are visited; shortestDistance will have the shortest distance for all cities from the origin)
  • How can all the routes be printed? (for each destination, use previousLocation to trace back the route)