467,878 Members | 1,263 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 467,878 developers. It's quick & easy.

Very urgent, please help - Min Time Cost Problem (Dijkstra’s algorithm)

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!
Nov 10 '07 #1
  • viewed: 2081
Share:
1 Reply
numberwhun
Expert Mod 2GB
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
Nov 10 '07 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

2 posts views Thread by Ricardo Batista | last post: by
3 posts views Thread by A_StClaire_ | last post: by
5 posts views Thread by A_StClaire_ | last post: by
3 posts views Thread by Ook | last post: by
1 post views Thread by chaos | last post: by
reply views Thread by MrMoon | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.