0

two tables Location and Routes. Location table contains following fields and values

id | name
1  | bangalore
2  | mumbai
3  | kolkatta
4  | delhi

Routes table contains following fields and values

id | source | desination
1  | 1    | 4
2  | 1    | 2
3  | 1    | 3
4  | 2    | 4
5  | 2    | 3
6  | 3    | 4

want to find all possible routes from source to destination like

 bangalore-delhi
    bangalore-mumbai-delhi
    bangalore-mumbai-kolkatta-delhi
    bangalore-kolkatta-delhi

please help me to achieve this result

Austin Rodrigues
  • 451
  • 5
  • 15
  • Firstly, rename your column 'from' & 'to' to something else as it's a reserved MySQL keyword. – Kitson88 Feb 07 '17 at 09:54
  • Something like this maybe? http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes – Yoshi Feb 07 '17 at 10:00
  • 1
    This could easily turn into the travelling salesman problem: https://www.google.co.uk/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=travelling+salesman+problem – ADyson Feb 07 '17 at 12:08

1 Answers1

0

Using your existing data from your two tables, you could LEFT JOIN columns source and destination from Routes meaning your INT values will match up to the Location.name column. Then make sure you order the data by source column for so it's easier to sort with PHP later on.

MySQL:

SELECT locStart.name as start, locFinish.name as finish FROM `routes` 
LEFT JOIN location as locStart
ON routes.source = locStart.id
LEFT JOIN location as locFinish
ON routes.destination = locFinish.id
ORDER BY routes.source

Output:

array (
  0 => 
  array (
    'start' => ' bangalore',
    'finish' => 'delhi',
  ),
  1 => 
  array (
    'start' => ' bangalore',
    'finish' => 'mumbai',
  ),
  2 => 
  array (
    'start' => ' bangalore',
    'finish' => 'kolkatta',
  ),
  //Etc....

Then add your DB results into multidimensional array using the Source name as the key.

$stmt = $pdo->query($query);
$result = $stmt->fetchAll(PDO::FETCH_ASSOC);
$newArr;

foreach ($result as $v) {

    $newArr[$v['start']][] = $v['finish'];
}

Output:

array (
  ' bangalore' => 
  array (
    0 => 'delhi',
    1 => 'mumbai',
    2 => 'kolkatta',
  ),
  'mumbai' => 
  array (
    0 => 'delhi',
    1 => 'kolkatta',
  ),
  'kolkatta' => 
  array (
    0 => 'delhi',
  ),
)

For outputting the new array, you can use a recursive function:

function recurse($newArr, $key=NULL) {

    if($key !== NULL) {
        foreach ($newArr[$key] as $k=>$v) {
            echo '<li>Destination: ' . $v . '</li>';
        } 

        echo '</ul>';

    } else {

        foreach ($newArr as $k=>$v) {
            echo 'Source: ' . $k . '<br><ul>';
            recurse($newArr, $k);
        }   
    } 
}

Output:

Source: bangalore

  • Destination: delhi
  • Destination: mumbai
  • Destination: kolkatta

Source: mumbai

  • Destination: delhi
  • Destination: kolkatta

Source: kolkatta

  • Destination: delhi
Kitson88
  • 2,889
  • 5
  • 22
  • 37