Как реконструировать дорожки из многолучевого Дейкстры?
В настоящее время я пишу библиотеку PHP для графиков. Я уже успешно реализовал односторонний алгоритм Дейкстры, но сейчас борюсь с реализацией многопутевой версии на этапе реконструкции пути.
Возьмите следующий график:
Этот граф, для простоты, имеет только пути от вершины 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
)
)
Текущий алгоритм восстановления пути Дейкстры с одним путем реализован следующим образом:
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, я соединяется с H, H соединяется с G, а G соединяется с A, в результате чего
$paths[3] = ['J', 'I', 'H', 'G', 'A']
Любая помощь будет оценена!
Решение
Как это? (Псевдокод):
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=[])
Другие решения
На самом деле, модифицированная функция DFS, которую я назвал «enumerate», решила этот вопрос. Ради потомков, вот код, который я использовал, чтобы превратить вывод многолучевого 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]);
}
}