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

实际上，我命名为“枚举”的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]);
}
}