Another Example
Previous    Next    Home    Package    Source    Queue class

Minimum number of hops
  1. Although messages move rapidly from one end of a Fiber Optics cable to the other, they encounter a significant delay when they are switched from one FO cable to another in an intermediate city. Hence, a message taking a path with fewest intermediate cities will arrive in less time than a message taking any other path (between the same two cities) with more intermediate cities even if such a path covers fewer miles.

    Now, suppose a communications company wants to choose the fastest communications route between a specified pair of cities for a given customer. That is, the communications company wants to select a path connecting specified cities Co and Cd over which messages reach their destination in the shortest time (that is, they encounter the minimum number of intermediate cities enroute) compared to all other possible paths between those cities. We need to provide a Java program that can choose the best path. The company will run the code and construct routing tables for the customer from the result.

  2. This solution uses Queue objects, one for each city, to store neighboring cities (those reachable in one hop). This is reasonable since the algorithm, which is demonstrated here, considers every neighboring city at most once.