Basic non-weighted pathfinding for list of start and end points

Question

I am making a tour project where I got stuck with a problem. I have created a database:

ID  Source   Destination

1     C1         C2
2     C3         c4
3     C3         C5
4     C4         C6
5     C8         C9
6     C2         C3

when I'm making a tour from C1->C6, it should follow the path c1->c2->c3->c4->c6. But when retrieving through a query I got conflicts when reaching c3: there is another C3->c5.

How can I overcome this problem?

first i am taking c1 as source by that checking in mysql from that i am getting destination by that destination taking as source checking related destination

How could the system know that going from c3 towards c6 must follow c3->c4 and not c3->c5 ? — jtheman, Nov 27 '12 at 06:32
@jtheman that's the point. user1702477, you have to try all paths. — John Dvorak, Nov 27 '12 at 06:37
Please refer this : http://stackoverflow.com/questions/11064913/achieve-hierarchy-in-a-less-number-of-mysql-queries — Sashi Kant, Nov 27 '12 at 07:15

Angelin Nadar · Answer 1 · 2012-12-03T15:03:14.523

1) You can solve by storing the the data into tree as foll and use algorithm to reach the destination:

enter image description here

2) A simple solution by using array and recursion:

Here the complex part would be only to bring the "required data for the mentioned source and destination" i.e leaving c8->c9

I havnt worked to do bring the foll data. But, you hane this you can proceed : $destination['c1'] = 'c2'; $destination['c3'][] = 'c4'; $destination['c4'] = 'c6'; $destination['c2'] = 'c3';

$route = array();
$int = 0;

function route_to($route,$source_statn, $dest_statn) {
    global $int, $destination,$path;

    if ($source_statn != '' && $dest_statn != '') {
        if ($destination[$source_statn] == $dest_statn) {
            $route[++$int] = "$source_statn -> {$destination[$source_statn]}";

            $path = $route;
            return $path;
        } else {
            if (is_array($destination[$source_statn])) {
                foreach ($destination[$source_statn] as $each) {
                    $route[++$int] = "$source_statn -> $each";
                    route_to($route,$each, $dest_statn);
                }
            } else {
                if($destination[$source_statn] != ''){
                    $route[++$int] = "$source_statn -> {$destination[$source_statn]}";
                }
                route_to($route,$destination[$source_statn], $dest_statn);
            }
        }
    }
}

route_to($route,'c1','c6');

echo '<pre>path';
print_r($path);
echo '</pre>';

---------o/p-----------

Array
(
    [1] => c1 -> c2
    [2] => c2 -> c3
    [3] => c3 -> c4
    [4] => c4 -> c6
)

here the complex part would be only to bring the "required data for the mentioned source and destination" — Angelin Nadar, Dec 03 '12 at 14:59

score 1 · Answer 2 · answered Nov 27 '12 at 10:06

1

Try:

CREATE TABLE test (
  ID INTEGER NOT NULL,
  SOURCE CHAR(2) NOT NULL,
  DESTINATION CHAR(2) NOT NULL
);

INSERT INTO test VALUES (1, 'C1', 'C2');
INSERT INTO test VALUES (2, 'C3', 'C4');
INSERT INTO test VALUES (3, 'C3', 'C5');
INSERT INTO test VALUES (4, 'C4', 'C6');
INSERT INTO test VALUES (5, 'C8', 'C9');
INSERT INTO test VALUES (6, 'C2', 'C3');

Then:

SELECT
  CONCAT_WS(
    '->',
    A.SOURCE,
    A.DESTINATION,
    B.DESTINATION,
    C.DESTINATION,
    D.DESTINATION
  )
FROM test A
LEFT JOIN test B ON B.SOURCE = A.DESTINATION
LEFT JOIN test C ON C.SOURCE = B.DESTINATION
LEFT JOIN test D ON D.SOURCE = C.DESTINATION
WHERE
  A.SOURCE = 'C1'
  AND 'C6' IN (A.DESTINATION, B.DESTINATION, C.DESTINATION, D.DESTINATION);

Which gives:

C1->C2->C3->C4->C6

Keep in mind that this example will only give paths with a maximum depth of 4, but you can easily extend this. Also you will get all possible paths (if there are multiple). So you need to decide which one you choose.

answered Nov 27 '12 at 10:06

eisberg

3,731
2
27
38

hi eisberg its very useful to me but if i add more source and destination then its not comming – nickle Nov 27 '12 at 10:45
@user1702477 What do you mean by more source and destination? Can you give an example? As I have stated in my answer it is possible to increase the search depth by adding more joins and extending A, B, C, D by E, F, G, a.s.o. – eisberg Nov 27 '12 at 10:46
yes but the thing is if he added more SOURCE and DESTINATION ...then how can i repeat A,B,c values..as they were adding dynamically...SOURCE and DESTINATION limit is not fixed – nickle Nov 27 '12 at 10:59
@user1702477 You might want to edit your question, so everyone gets a chance to understand your problem. Give a more detailed example and output you want as well as output you do not want. – eisberg Nov 27 '12 at 11:55

Basic non-weighted pathfinding for list of start and end points

2 Answers2