13,089,943 members (42,217 online)
Rate this:
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 28-Feb-13 1:55am
velvet71.1K

Rate this:

## 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).
velvet7 1-Mar-13 3:27am

Exactly what I was looking for, thank you. :)
velvet7 3-Mar-13 8:28am

"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.

Top Experts
Last 24hrsThis month
 Richard Deeming 220 ProgramFOX 160 Graeme_Grant 150 OriginalGriff 150 ppolymorphe 90
 OriginalGriff 3,412 Graeme_Grant 1,874 ProgramFOX 1,707 Jochen Arndt 1,645 ppolymorphe 1,507