如何从多路径 Dijkstra 重建路径？

Question

我目前正在编写一个 PHP 图形库。我已经成功实现了单路径 Dijkstra 算法，但现在在路径重构阶段实现多路径版本时遇到困难。

取下图：

此图为了简单起见，只有从顶点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
        )

)

当前的单路径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]
    );
}

有没有办法修改上面的内容，使 return 包含 paths 数组中的所有路径？我已经考虑过使用堆栈或 DFS，但无法提出解决方案。我还尝试了 foreach 循环和递归，但无济于事。

我本质上想要发生的是按如下方式处理的结果：

J 连接到 B，B 连接到 A，因此 $paths[0] = ['J', 'B', 'A']
J 连接到 F，F 连接到 E 和 D，因此继续通过 E，记住 return 到 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']

如有任何帮助，我们将不胜感激！

Answer 1

像这样？（伪代码）：

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=[])

Answer 2

实际上，我命名为 "enumerate" 的修改后的 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]);
    }
}

如何从多路径 Dijkstra 重建路径？

How to reconstruct paths from a multi-path Dijkstra?

php

algorithm

graph

path

dijkstra