Click here to Skip to main content
13,089,943 members (42,217 online)
Rate this:
Please Sign up or sign in to vote.
See more:

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

1 solution

Rate this: bad
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).
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

Advertise | Privacy |
Web03 | 2.8.170813.1 | Last Updated 28 Feb 2013
Copyright © CodeProject, 1999-2017
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