Actualmente estoy escribiendo una biblioteca PHP para gráficos. Ya he implementado un algoritmo de Dijkstra de ruta única con éxito, pero ahora tengo dificultades para implementar una versión de ruta múltiple en la etapa de reconstrucción de ruta.

Tome el siguiente gráfico:

Este gráfico, en aras de la simplicidad, solo tiene rutas desde el vértice A hasta J, pasando por varios vértices múltiples, que son todos iguales en costo, es decir, el peso del borde para cada ruta suma hasta 10. El Dijkstra modificado produce correctamente la siguiente salida (que es la 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
        )

)

El algoritmo actual de reconstrucción de ruta Dijkstra de ruta única se implementa como tal:

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

¿Hay alguna manera de modificar lo anterior, de modo que me devuelva todos los caminos en unpaths ¿formación? Ya he pensado en usar quizás una pila o DFS, pero no pude encontrar una solución. También diforeach bucles y recursión un intento, en vano.

Lo que esencialmente quiero que suceda es que el resultado se procese de la siguiente manera:

J se conecta a B, B se conecta a A, por lo tanto$paths[0] = ['J', 'B', 'A']J se conecta a F, F se conecta a E y D, por lo tanto, continúe a través de E, recordando regresar a F, luego cree otra ruta a través de D, lo que resulta enpaths[1] = ['J', 'F', 'E', 'C', 'A'] y$paths[2] = ['J', 'F', 'D', 'C', 'A']J se conecta a I, me conecto a H, H se conecta a G y G se conecta a A, lo que resulta en$paths[3] = ['J', 'I', 'H', 'G', 'A']

¡Cualquier ayuda sería apreciada!