gpt4 book ai didi

php - 如何从多路径 Dijkstra 重建路径?

转载 作者:搜寻专家 更新时间:2023-10-31 21:50:40 25 4
gpt4 key购买 nike

我目前正在编写一个用于图形的 PHP 库。我已经成功地实现了单路径 Dijkstra 算法,但现在在路径重建阶段难以实现多路径版本。

取下图:

Graph

这个图为了简单起见,只有从顶点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]
);
}

有没有办法修改上面的内容,以便它返回 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']

如有任何帮助,我们将不胜感激!

最佳答案

实际上,我命名为“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]);
}
}

关于php - 如何从多路径 Dijkstra 重建路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43901833/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com