find shortest path

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
Think Pink
Forum Contributor
Posts: 106
Joined: Mon Aug 02, 2004 3:29 pm

find shortest path

Post 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.
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Re: find shortest path

Post 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.
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Re: find shortest path

Post 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.
User avatar
Think Pink
Forum Contributor
Posts: 106
Joined: Mon Aug 02, 2004 3:29 pm

Re: find shortest path

Post 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:
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Re: find shortest path

Post 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.
Post Reply