15,665,444 members
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

## 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).

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)

Top Experts
Last 24hrsThis month
 OriginalGriff 140 Richard Deeming 80 Dave Kreskowiak 70 George Swan 35 Andre Oosthuizen 25
 OriginalGriff 2,433 Graeme_Grant 1,110 Richard Deeming 888 Richard MacCutchan 673 Dave Kreskowiak 601

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