Find all possible paths on a graph

find-graph-paths.php

<?php

$graph = [
    ['A', 'B'],
    ['A', 'D'],
    ['A', 'E'],
    ['B', 'E'],
    ['B', 'C'],
    ['D', 'C'],
    ['D', 'K'],
    ['E', 'F'],
    ['E', 'B'],
    ['F', 'G'],
    ['G', 'K'],
    ['C', 'K'],
];

function findPaths(array $graph, $from, $to)
{
    $startPaths = $graph;

    // Search all possible start points
    // and removed them from possible next path
    foreach ($startPaths as $key => $path) {
        if ($path[0] != $from) {
            unset($startPaths[$key]);
        } else {
            unset($graph[$key]);
        }
    }

    // No start point found
    if (count($startPaths) == 0) {
        return false;
    }

    // Test all possible start points
    $stackPath = [];
    foreach($startPaths as $path) {

        if ($path[1] == $to) {
            return $path[0].$path[1];
        }

        if (!$found = findPaths($graph, $path[1], $to)) {
            continue;
        }

        $stackPath[$path[0].$path[1]] = $found;
    }

    return $stackPath;
}

$paths = findPaths($graph, 'A', 'K');

// ---------------------------------------------
// All following code is only for visual purpose

function flatArray($paths, $pre = '', $lines = []) {
    foreach($paths as $key => $path) {
        if (is_array($path)) {
            $lines = flatArray($path, $pre.$key.' | ', $lines);
        } else {
            $lines[] = $pre.$key.' | '.$path;
        }
    }
    return $lines;
}

if (is_array($paths)) {
    $lines = flatArray($paths);

    usort($lines, function($a, $b) {
        $al = strlen($a);
        $bl = strlen($b);

        if ($al == $bl) { return 0; }
        return ($al < $bl) ? -1 : 1;
    });

    foreach ($lines as $line) {
        echo $line,"\n";
    }
} else {
    echo 'Can\'t find valid path.';
}

output

AD | DK
AB | BC | CK
AE | EF | FG | GK
AE | EB | BC | CK
AB | BE | EF | FG | GK

returned array

array(3) {
  ["AB"]=>
  array(2) {
    ["BE"]=>
    array(1) {
      ["EF"]=>
      array(1) {
        ["FG"]=>
        string(2) "GK"
      }
    }
    ["BC"]=>
    string(2) "CK"
  }
  ["AD"]=>
  string(2) "DK"
  ["AE"]=>
  array(2) {
    ["EF"]=>
    array(1) {
      ["FG"]=>
      string(2) "GK"
    }
    ["EB"]=>
    array(1) {
      ["BC"]=>
      string(2) "CK"
    }
  }
}