<?php
/*Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию
Легко доработать до поиска кратчайшего пути.*/

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

// Упорядоченный граф
$a = array('b', 'c', 'd');
$b = array('d', 'e', 'f');
$c = array('d', 'e', 'f');
$d = array('e', 'f');
$e = array('f');
$f = array();

// Первый путь
$x = array('a', 'b', 'd', 'e', 'f');

// Массив соответствий
$arr = array('a' => $a, 'b' => $b, 'c' => $c, 'd' => $d, 'e' => $e, 'f' => $f);

// Печатаем первый маршрут
print_r($x);
print "\n";

$j = count($x) - 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {

    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        //найдем все 0-ые индексы
        $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == 'f') {
                array_push($x, $z);
                break;
            }
            array_push($x, $z);
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];
        }
        $j = count($x);
        print_r($x);
    }
    $j--;
}
?>