我正在编写一个关于图表的PHP库。目前,我已经成功实现了单路径迪杰斯特拉算法,但是在多路径重建阶段却遇到了困难。
以下是一张示例图表:
此图表只有从A到J的路径,通过多个其他点,这些点的代价相等,即每条路径的边权值加起来都为10。经过修改的迪杰斯特拉算法正确输出以下结果(数组
目前,单路径 Dijkstra 路径重建算法的实现如下:
有没有一种方法可以修改上面的代码,以便它将所有路径返回给我,并存储在一个名为
我想要的结果实际上是按以下方式处理:
- J连接到B,B连接到A,因此
以下是一张示例图表:
此图表只有从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']
任何帮助都将不胜感激!