如何从多路径Dijkstra重构路径? [英] How to reconstruct paths from a multi-path Dijkstra?

问题描述

我目前正在为图形编写PHP库.我已经成功实现了单路径Dijkstra的算法，但是现在在路径重构阶段难以实现多路径版本.

I am currently writing a PHP library for graphs. I have already implemented a single-path Dijkstra's algorithm successfully, but now struggle with implementing a multi-path version at the path reconstruction stage.

拍摄以下图形:

为简单起见，此图仅具有从顶点A到J的路径，并经过多个其他顶点，这些顶点的成本均相等，也就是说，每条路径的边权重总计为10. Dijkstra正确产生以下输出(它是数组$this->prev):

This graph, for the sake of simplicity, has only paths from vertex A to J, going through multiple other vertices, which are all equal in cost, that is, the edge weight for each path add up to 10. The modified Dijkstra correctly produces the following output (which is the array $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路径重构算法是这样实现的:

The current, single-path Dijkstra path reconstruction algorithm is implemented as such:

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循环和递归，但无济于事.

Is there a way to modify the above, such that it returns me all the paths in a paths array? I have already thought about using maybe a stack or DFS, but couldn't come up with a solution. I also gave foreach loops and recursion a try, to no avail.

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

What I essentially want to happen is the result to be processed as follows:

• 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']

• J connects to B, B connects to A, hence $paths[0] = ['J', 'B', 'A']
• J connects to F, F connects to E and D, hence continue on through E, remembering to return to F, then create another path through D, resulting in paths[1] = ['J', 'F', 'E', 'C', 'A'] and $paths[2] = ['J', 'F', 'D', 'C', 'A']
• J connects to I, I connects to H, H connects to G and G connects to A, resulting in $paths[3] = ['J', 'I', 'H', 'G', 'A']

任何帮助将不胜感激！

推荐答案

实际上，我命名为"enumerate"的一个经过修改的DFS函数解决了这个问题.为了后人，这是我用来将多路径Dijkstra的输出转换为路径数组的代码:

Actually, a modified DFS function I named "enumerate" solved this question. For posterity's sake, here is the code I used to turn the output of the multi-path Dijkstra into an array of paths:

/**
 * 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重构路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！