Click here to Skip to main content
15,867,594 members
Please Sign up or sign in to vote.
5.00/5 (5 votes)
See more:
Hi,

I have already seen a lot of methods to find the right path from point A to B. (Astar, dijkstra, etc.)

Now what I am trying to solve is something else, and i don't know if anyone have ever done something like this before...

I'll try to explain.

Let's say I have point A, B, and C.
Between these points there's a given speed limit, let's say A-B 20km/h, A-C, 10km/h, B-C 20km/h, and the distances are: A-B 5km, A-C 10km, B-C 5km.

Now I have to find the "fastest" path from A to C. Now it would seem easier to go form A to C directly, but it is definitely not the fastest.

I could create a recursive call to check every possible path, but when I have thousands of points it would become kinda slow.
Posted

1 solution

That is called a weighted graph (where each edge has a "cost"). The "cost" in your case would be the total time to travel from one node to the next (which can be calculated with the inputs you specified, speed and distance).

You mentioned one possible solution already: Dijkstra's algorithm, which works for weighted graphs.

Now, if A-B is different than B-A, that'd be more interesting (it appears, however, that the "roads" you are describing are the same speed in both directions).
 
Share this answer
 
Comments
velvet7 1-Mar-13 3:27am    
Exactly what I was looking for, thank you. :)
velvet7 3-Mar-13 8:28am    
By the way, I was thinking about this lately:
"if A-B is different than B-A, that'd be more interesting".
Why would it be more interesting?
As I understood Dijkstra's algorithm it would work for this one perfectly as well. (and I tried it as well, and there weren't any problems)
Am I missing something here?
AspDotNetDev 3-Mar-13 19:31pm    
For one, the data structure would be more interesting, because then you wouldn't be storing one cost per edge, but two. However, Dijkstra's algorithm may work for that too... I haven't really thought about it. I only mentioned it so that you would consider that possibility and that there may or may not be further implications to consider.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900