如何从多路径Dijkstra算法中重构路径？

Question

我正在编写一个关于图表的PHP库。目前，我已经成功实现了单路径迪杰斯特拉算法，但是在多路径重建阶段却遇到了困难。

以下是一张示例图表：

此图表只有从A到J的路径，通过多个其他点，这些点的代价相等，即每条路径的边权值加起来都为10。经过修改的迪杰斯特拉算法正确输出以下结果（数组$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
        )

)

目前，单路径 Dijkstra 路径重建算法的实现如下：

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，I连接到H，H连接到G和G连接到A，结果为$paths [3] = ['J'，'I'，'H'，'G'，'A'] 任何帮助都将不胜感激！

- algrithmic

Answer 1

实际上，我修改了DFS函数并将其命名为“枚举”，解决了这个问题。为了后人着想，这里是我用来将多路径Dijkstra的输出转换为路径数组的代码：

/**
 * Returns all shortest paths to $dest from the origin vertex $this->start in the graph.
 *
 * @param string $dest ID of the destination vertex
 *
 * @return array An array containing the shortest path and distance
 */
public function get($dest)
{
    $this->paths = [];
    $this->enumerate($dest, $this->start);

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

/**
 * Enumerates the result of the multi-path Dijkstra as paths.
 *
 * @param string $source ID of the source vertex
 * @param string $dest   ID of the destination vertex
 */
private function enumerate($source, $dest)
{
    array_unshift($this->path, $source);
    $discovered[] = $source;

    if ($source === $dest) {
        $this->paths[] = $this->path;
    } else {
        if (!$this->prev[$source]) {
            return;
        }
        foreach ($this->prev[$source] as $child) {
            if (!in_array($child, $discovered)) {
                $this->enumerate($child, $dest);
            }
        }
    }

    array_shift($this->path);
    if (($key = array_search($source, $discovered)) !== false) {
        unset($discovered[$key]);
    }
}

- algrithmic

Answer 2

像这样吗？（伪代码）：

function output_paths(source, dest, tail) {

    if source == dest:
        output([dest] + tail)

    for each node in prev[dest]:
        output_paths(source, node, [dest] + tail)
}


output_paths(source=A, dest=J, tail=[])

- tiwo