Min Time Cost Problem (Dijkstra’s algorithm)

[victorporton]

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 looooooooooooot in advence!

[numberwhun]

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 looooooooooooot in advence!

Sorry, but nobody here is going to do your homework for you. If you read the forum Posting Guidelines, you will find that it is against the site policy to post homework questions.

Regards,

Moderator

[SwissProgrammer]

victorporton,

Read my post at https://bytes.com/topic/c/answers/97...ap-help-please and see how I am (currently) attempting to get help with a "useable" shortest path algorithm. A lot of people have run their mouth on other sites about how to create a shortest path algorithm, but not one of those worked for me. So, I came here. See what I did and start there if it helps.

I still have NOT gotten it to work.

[SwissProgrammer]

Update:

Not there yet.