CODEWITHSUNDEEP
algorithmdistancegraph-algorithmdijkstra
Fabdrol
Fabdrol

Reputation: 738

path finding: calculating the optimal path, where “optimal” means maximum distance within a given time

Not sure if this is the right place to ask this, but here's my problem:

I have a large set of points, where each point represents a coordinate. I need to develop an algorithm that calculates which points to visit in order to maximise the total distance travelled within a certain time span (e.g., 24 hours). For each path between two points I know the distance and the maximum speed.

In addition, there's a constraint. Each path can only be travelled twice (so, up and down is possible but then both points cannot be used again).

My problem is: I don't know where to start. I've looked at some pathfinding algorithms (eg Dijkstra's), but they're all to find the least distance whereas I need to find the maximum distance!

Upvotes: 2

Views: 847

Answers (1)

mickeyandkaka
mickeyandkaka

Reputation: 1457

If the time is integer and not too big, you can use dynamic programming.

create dp[pos][t]

which means currently in time t, you are in positon pos, the maximun distance you can achieve.

then your answer is the maximun value of {dp[destinatin][valid_time]}.

dp[][] can be calculated like dijkstra or spfa algorithm.

Hope this can help you a bit.

Upvotes: 0

Related Questions