find shortest path
Posted: Thu Jun 26, 2008 9:22 am
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.
places in table_1
time is in minutes
in [table_2] let's say I have the following routes.
... 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 ...
... but if he selects max 2 changes then, only the following results would be returned
I hope you follow me so far ...
Now, this is the function I thought I could use.
to call this function would be (remember, user wants to go from A to G with 2 max changes.)
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.
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
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)
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
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
Code: Select all
A -> E -> F -> G
A -> E -> G
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);
}
}
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);
$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.