Atualmente, estou escrevendo uma biblioteca PHP para gráficos. Eu já implementei o algoritmo de Dijkstra de caminho único com êxito, mas agora luto com a implementação de uma versão de caminhos múltiplos no estágio de reconstrução do caminho.

Veja o seguinte gráfico:

Este gráfico, por uma questão de simplicidade, possui apenas caminhos do vértice A a J, passando por vários outros vértices, todos com o mesmo custo, ou seja, o peso da borda de cada caminho é igual a 10. O Dijkstra modificado produz corretamente a seguinte saída (que é a matriz$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
        )

)

O atual algoritmo de reconstrução de caminho Dijkstra de caminho único é implementado da seguinte forma:

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]
    );
}

Existe uma maneira de modificar o acima, de modo que ele me retorne todos os caminhos em umpaths matriz? Eu já pensei em usar talvez uma pilha ou DFS, mas não consegui encontrar uma solução. Eu também deiforeach loops e recursão uma tentativa, sem sucesso.

O que eu essencialmente quero que aconteça é o resultado a ser processado da seguinte maneira:

J se conecta a B, B se conecta a A, portanto$paths[0] = ['J', 'B', 'A']J se conecta a F, F se conecta a E e D; portanto, continue com E, lembrando-se de retornar a F e, em seguida, crie outro caminho através de D, resultando empaths[1] = ['J', 'F', 'E', 'C', 'A'] e$paths[2] = ['J', 'F', 'D', 'C', 'A']J se conecta a I, eu se conecta a H, H se conecta a G e G se conecta a A, resultando em$paths[3] = ['J', 'I', 'H', 'G', 'A']

Qualquer ajuda seria apreciada!