тоящее время я пишу библиотеку PHP для графиков. Я уже успешно реализовал односторонний алгоритм Дейкстры, но сейчас борюсь с реализацией многопутевой версии на этапе реконструкции пути.

Возьмите следующий график:

Этот граф, для простоты, имеет только пути от вершины A до J, проходящие через множество других вершин, которые все равны по стоимости, то есть вес ребра для каждого пути складывается до 10. Модифицированный Dijkstra правильно производит следующий вывод (который является массивом$this->prev):

Array
(
    [A] => 
    [B] => Array
        (
            [0] => A
        )

    [C] => Array
        (
            [0] => A
        )

    [D] => Array
        (
            [0] => C
        )

    [E] => Array
        (
            [0] => C
        )

    [F] => Array
        (
            [0] => E
            [1] => D
        )

    [G] => Array
        (
            [0] => A
        )

    [H] => Array
        (
            [0] => G
        )

    [I] => Array
        (
            [0] => H
        )

    [J] => Array
        (
            [0] => B
            [1] => F
            [2] => I
        )

)

Текущий алгоритм восстановления пути Дейкстры с одним путем реализован следующим образом:

public function get($dest)
{
    $destReal = $dest;
    $path = array();
    while (isset($this->prev[$dest])) {
        array_unshift($path, $dest);
        $dest = $this->prev[$dest];
    }
    if ($dest === $this->start) {
        array_unshift($path, $dest);
    }

    return array(
        'path' => $path,
        'dist' => $this->dist[$destReal]
    );
}

Есть ли способ изменить выше, так что он возвращает мне все пути вpaths массив? Я уже думал об использовании стека или DFS, но не смог найти решение. Я также далforeach петли и рекурсия попробовать, но безрезультатно.

По сути, я хочу, чтобы результат обрабатывался следующим образом:

J соединяется с B, B соединяется с A, следовательно$paths[0] = ['J', 'B', 'A']J соединяется с F, F соединяется с E и D, следовательно, продолжается через E, не забывая возвращаться к F, затем создает другой путь через D, что приводит кpaths[1] = ['J', 'F', 'E', 'C', 'A'] а также$paths[2] = ['J', 'F', 'D', 'C', 'A']J подключается к I, я подключаюсь к H, H подключается к G и G подключается к A, в результате чего$paths[3] = ['J', 'I', 'H', 'G', 'A']

Любая помощь будет оценена!