D.K. is traveling from City A to City B. He can stop at some designated spots only.
I am trying to use Dijkstra’s algorithm to determine the “spot-to-spot” path that will get D.K. from City A to the City B in the minimum amount of time.
The input in my program is an integer n and the 2D coordinates of n spots.
Some assumptions have been made about the physical layout of the problem:
1) All the spots are considered to be in a square of side 1600 km. A coordinate system is laid out for this square so that the lower left corner of the square is at the origin.
2) The coordinates of City A are (0, 1600) and the City B is at (1600, 0).
3) There is no “clumping” of spots. This means that for any pair of spots, the difference in their xcoordinates is >= 40 km or the difference in their y-coordinates is >= 40 km.
4) As the input size n increases for other problem instances, the clumping constraint may require that the area of the square must also increase. In other words, I am not allowed to assume that the number of spots is bounded above by some constant.
In addition, D.K. may choose to travel at either speed of the following:
Option 1: D.K. can travel at 10 km/hr but can only travel for 10 hours at this speed when he is still energetic
Option 2: D.K. can travel faster at 20 km/hr but can only last for 5 hours even though he has been out of energy.
That is, D.K. can travel up to 200km between spots: travel at 10km/hr for 10 hours and then travel at 20 km/hr for 5 hours.
(Because of these constraints, it is quite possible to have input data that will cause the algorithm to claim that the trip from City A to the City B cannot be done)
It is obvious that there is a limitation on distance traveled between spots because of the time limitations imposed by the constraints above, so I don’t want to use a complete graph to describe the distances between all the spots. I want a sparse graph represented by an adjacency list instead.
However, this adjacency list is built only after building a data structure that can provide a list of spots that are close by to any given spot. Once this is accomplished, I can add time costs to the graph edges.
So, my question is how I should build the data structure that can satisfy the following query: For a given “query” spot Q, find all nearby spots.
Could someone kindly suggest some pseudo-code that describes how the data structure is built? And I hope the construction of the adjacency list is faster than theta(n^2).
Thanks a loooooooooooooo t in advance!!
I am trying to use Dijkstra’s algorithm to determine the “spot-to-spot” path that will get D.K. from City A to the City B in the minimum amount of time.
The input in my program is an integer n and the 2D coordinates of n spots.
Some assumptions have been made about the physical layout of the problem:
1) All the spots are considered to be in a square of side 1600 km. A coordinate system is laid out for this square so that the lower left corner of the square is at the origin.
2) The coordinates of City A are (0, 1600) and the City B is at (1600, 0).
3) There is no “clumping” of spots. This means that for any pair of spots, the difference in their xcoordinates is >= 40 km or the difference in their y-coordinates is >= 40 km.
4) As the input size n increases for other problem instances, the clumping constraint may require that the area of the square must also increase. In other words, I am not allowed to assume that the number of spots is bounded above by some constant.
In addition, D.K. may choose to travel at either speed of the following:
Option 1: D.K. can travel at 10 km/hr but can only travel for 10 hours at this speed when he is still energetic
Option 2: D.K. can travel faster at 20 km/hr but can only last for 5 hours even though he has been out of energy.
That is, D.K. can travel up to 200km between spots: travel at 10km/hr for 10 hours and then travel at 20 km/hr for 5 hours.
(Because of these constraints, it is quite possible to have input data that will cause the algorithm to claim that the trip from City A to the City B cannot be done)
It is obvious that there is a limitation on distance traveled between spots because of the time limitations imposed by the constraints above, so I don’t want to use a complete graph to describe the distances between all the spots. I want a sparse graph represented by an adjacency list instead.
However, this adjacency list is built only after building a data structure that can provide a list of spots that are close by to any given spot. Once this is accomplished, I can add time costs to the graph edges.
So, my question is how I should build the data structure that can satisfy the following query: For a given “query” spot Q, find all nearby spots.
Could someone kindly suggest some pseudo-code that describes how the data structure is built? And I hope the construction of the adjacency list is faster than theta(n^2).
Thanks a loooooooooooooo t in advance!!
Comment