CODEWITHSUNDEEP
phpmysql
nickle
nickle

Reputation: 5196

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

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

Upvotes: 0

Views: 119

Answers (2)

Angelin Nadar
Angelin Nadar

Reputation: 9300

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
)

Upvotes: 1

eisberg
eisberg

Reputation: 3771

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.

Upvotes: 1

Related Questions