CODEWITHSUNDEEP
phppathnodes
sarotnem
sarotnem

Reputation: 349

PHP Find path in multidimensional array

Let's assume that we have an array with a number of arrays defining paths to specific nodes. For example:

X1     X3     X5     
|      |      |      
A  --  B  --  C  --  D
|      |      |      
X2     X4     X6

and with code:

$array = [
  'A' => ['B','X1','X2'],
  'B' => ['C','X3','X4'],
  'C' => ['D','X5','X6'],
];

What is the best way to find the path from one point to another with a maximum of 2 nodes? For example to get from A to D you need to hop from A to B to C and then to D.

Right now I have written a function that does this search but I'm sure that there is a better way to do this search (maybe a recursive one).

private function findpath($array, $start, $end)
{
    $result = array();

    foreach ($array[$start] as $key1 => $value1) {
        foreach ($array[$value1] as $key2 => $value2) {
                if (in_array($end, $array[$value2])) {
                    return $result = [$start, $value1, $value2, $end];
                }
        }
    }
} 

findpath($array, 'A', 'D');

// returns
// array:4 [
  // 0 => "A"
  // 1 => "B"
  // 2 => "C"
  // 3 => "D"
// ]

Upvotes: 0

Views: 314

Answers (1)

astrangeloop
astrangeloop

Reputation: 1520

One possible approach would be to use a stack as a list of paths that are to be checked. In a loop you could remove a path from the stack, check if it has found the target, and if not, generate new paths by finding next steps in your $array of nodes, and then add the new paths to the stack to be checked by the next iteration of the loop. If the stack becomes empty it means that no path from start to end could be found.

The original $array you provided would not allow paths to loop around or repeat, but for testing purposes I have extended your array, assuming that all nodes are fully connected:

$array = [
    'A' => ['B','X1','X2'],
    'B' => ['A', 'C','X3','X4'],
    'C' => ['B', 'D','X5','X6'],
    'D' => ['C'],
    'X1' => ['A'],
    'X2' => ['A'],
    'X3' => ['B'],
    'X4' => ['B'],
    'X5' => ['C'],
    'X6' => ['C'],
];

Given this, it's also a good idea to maintain a separate list of nodes already visited, so that the code doesn't revisit nodes or get stuck in a looping path.

This function will find the shortest path between two nodes, or return false of no path could be found (tested with php 5.6):

function findpath(array $array, $start, $end, $steps = null)
{
    $visited = []; // keep track of nodes already visited to avoid loops
    $paths = [[$start]]; // array of paths to be checked
    while ($path = array_pop($paths)) {
        $node = end($path);
        if ($node === $end) {
            return $path; // found path from start to end node
        }
        if ($steps !== null && count($path) > $steps) {
            continue; // path too long
        }
        $visited[$node] = true;
        if (empty($array[$node])) {
            continue; // can't reach any other nodes from this path
        }
        foreach ($array[$node] as $next) {
            if (isset($visited[$next])) {
                continue; // already visited next node
            }
            // make new path by adding next node to current path
            // then add new path to array of paths to be checked
            $paths[] = array_merge($path, [$next]);
        }
    }
    return false; // no paths left to check, cannot find path from start to end node
}

You can optionally provide a maximum number of steps to the function (for example the path A -> B -> C -> D is 3 steps):

var_dump(findPath($array, 'A', 'D', 3));
// returns ['A', 'B', 'C', 'D']

var_dump(findPath($array, 'A', 'D', 2));
// returns false as path would be longer than 2 steps

var_dump(findPath($array, 'X1', 'X6'));
// returns ['X1', 'A', 'B', 'C', 'X6']

Upvotes: 1

Related Questions