Page 1 of 1

find shortest path

Posted: Thu Jun 26, 2008 9:22 am
by Think Pink
Hello,
please advice with the following.

I want to be able to calculate shortest route and time for some mountain trails. I'll try to explain in coding a little better than in words.

Code: Select all

 
[table_1]
id integer, autoincrement
name varchar
 
places in table_1

Code: Select all

 
id   |   name
1    |   A
2    |   B
3    |   C
4    |   D
5    |   E
6    |   F
7    |   G
8    |   H
9    |   I
10  |   J
.....
 

Code: Select all

 
[table_2]
id integer, autoincrement
from varchar(16)
to varchar(16)
time varchar(6)
 
time is in minutes

in [table_2] let's say I have the following routes.

Code: Select all

 
From     |     To        |     time
A         |      B       |      200
A         |      C       |      215
B         |      C       |      140
B         |      C       |      60
C         |      A       |      190
D         |      B       |      45
D         |      E       |      15
A         |      E       |      25
B         |      E       |      48
B         |      F       |      25
C         |      E       |      40
E         |      F       |      125
F         |      G       |      100
D         |      G       |      60
E         |      G       |      120
G         |      H       |      15
H         |      I        |      25
G         |      M       |      160   
 
... a user would like to find shortest way from A to B with 3 maximum changes / stops (you know like in trainstations when you want to go from Madrid to Hamburg and there is no direct train. Then you would have to change in Zurich and then in Berlin) just a silly example.

More explanation.
...if a user would like to go from A to G with a direct route (without changes) as you can see from above is not possible.
...if a user would like to go from A to G (with a high number of changes) the following results will be returned ...

Code: Select all

 
A -> B -> C -> E -> F -> G
A -> B -> C -> E -> G
A -> E -> F -> G
A -> E -> G
 
... but if he selects max 2 changes then, only the following results would be returned

Code: Select all

 
A -> E -> F -> G
A -> E -> G
 
I hope you follow me so far ...

Now, this is the function I thought I could use.

Code: Select all

 
function find_routes ($start, $end, $from, $to, $maxchanges, $changes){
$q = $d->query("SELECT * FROM table_2 WHERE  from='".$from."' ");
while($r = $q->fetchdata()){
if($end == $r['to']){
    echo 'found one direct route';
}
elseif ($maxchanges <= $changes) {
    find_routes ($start, $end, $r['from'], $r['to'], $maxchanges, $changes + 1);
}
}
 
to call this function would be (remember, user wants to go from A to G with 2 max changes.)

Code: Select all

 
$start = 1; // (the Id for point A is 1 - from the table_1)
$end = 7; // (the Id for point G is 7)
$maxchanges = 2;
 
find_routes ($start, $end, $start, $end, $maxchanges, 0);
 
all outputs are in one array something like this
$results = array([0] => array([0] => 1, [1] => 5, [2] => 7)) then the times are being calculated (sum). for all top level arrays.

maybe you also have some recomandations on how I could put results in array?
example
from id 1 to id 5 to id 7 == (A -> E -> G) == 145minutes

OK, the function above is with what I came up. Do you have to recommend another way of doing things? Or maybe some advice? I didn't start actually working on things, because first I wanted to share with you my thoughts. Maybe someone else will benefit from this.

Re: find shortest path

Posted: Thu Jun 26, 2008 11:21 am
by Kieran Huggins
you may find http://en.wikipedia.org/wiki/Shortest_path_problem interesting

I'm currently working on a project that incorporates a trip planner for public transit data, and I've come to respect the complexity of finding the shortest path though a graph.

You might also keep in mind that the complexity grows geometrically with the number of vertices in your graph, but for a small dataset like your example it shouldn't be a problem.

Re: find shortest path

Posted: Thu Jun 26, 2008 11:33 am
by jayshields
I haven't read your whole post, but I too have studied this before. Some things you might want to read about: Dijkstra's Algorithm and Floyd-Warshall's Algorithm for directed graphs and maybe Kruskal's Alrorithm for minimum spanning trees. If you have any trouble finding good material on these topics send me a PM and I'll link you/send you some good lecture notes I have.

Sometimes problems like this require unbounded exhaustive search algorithms. Which means you have to attempt every route to find the shortest path and at any point may have to undo every action already taken. A common example of this is the travelling salesman problem. These types of algorithms are exponential (n^n), and as data sets grow to a certain extent, these algorithms are completely infeasible.

Re: find shortest path

Posted: Thu Jun 26, 2008 1:39 pm
by Think Pink
I found something about this.
Maybe there is someone else who is interesting and maybe working with this.

First read this to understand the thing ...
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
http://www.dgp.toronto.edu/people/James ... pplet.html

And the coding ...
http://forums.bots-united.com/showthread.php?t=3055
http://codeguru.earthweb.com/forum/show ... p?t=430962
http://en.giswiki.net/wiki/Dijkstra%27s_algorithm

However, this thread is not closed yet. :banghead:

Re: find shortest path

Posted: Thu Jun 26, 2008 1:46 pm
by Kieran Huggins
I have this theory that you may be able to leverage the power of modern GPUs (which are hella fast) for this kind of problem by essentially modeling the graph in 3d.

Though I was looking at the shortest path problem in the sense that there are fixed trips between nodes, so it adds another dimension to the problem set.

Any experienced GL people out there who can comment?

*disclaimer: this is probably complete <span style='color:blue' title='I&#39;m naughty, are you naughty?'>smurf</span>. really.