Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C# .NET maths
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 28-Feb-13 2:55am
velvet71.1K

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

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).
  Permalink  
Comments
velvet7 at 1-Mar-13 3:27am
   
Exactly what I was looking for, thank you. :)
velvet7 at 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 at 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
0 OriginalGriff 350
1 Jochen Arndt 190
2 Richard MacCutchan 135
3 Sergey Alexandrovich Kryukov 130
4 DamithSL 105
0 OriginalGriff 6,045
1 DamithSL 4,601
2 Maciej Los 4,087
3 Kornfeld Eliyahu Peter 3,480
4 Sergey Alexandrovich Kryukov 3,310


Advertise | Privacy | Mobile
Web02 | 2.8.141220.1 | Last Updated 28 Feb 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100