다중 경로 Dijkstra에서 경로를 재구성하는 방법은 무엇입니까?

현재 그래프 용 PHP 라이브러리를 작성 중입니다. 이미 단일 경로 Dijkstra의 알고리즘을 성공적으로 구현했지만 경로 재구성 단계에서 다중 경로 버전을 구현하는 데 어려움을 겪고 있습니다.다중 경로 Dijkstra에서 경로를 재구성하는 방법은 무엇입니까?

테이크 다음 그래프 :

이 그래프는, 간단하게하기 위해, 즉 모든 비용이 동일한 여러 다른 정점을 통과, J에 정점 A를 만 경로가

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 
     ) 

)

현재, 단일 경로 익스트라 경로 재구성 ALG : 각 경로에 대한 에지 웨이트 개질 익스트라 올바르게 (배열 $this->prev 임) 다음과 같은 출력을 생성한다 (10)에 추가 할 orithm 같은 구현됩니다

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 루프와 재귀를 시도했다. 아무 소용이 없다.

무엇 I 본질적 발생하고자하면 다음과 같이 처리 할 수있는 결과이다

J는 B가 연결, B에 연결 따라서 $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에 연결되고 H는 G에 연결되고 G는 A에 연결됩니다. in $paths[3] = ['J', 'I', 'H', 'G', 'A']

도움이 될 것입니다.

출처

2017-05-10 algrithmic

실제로 "열거"라는 이름의 수정 된 DFS 함수가이 질문을 해결했습니다. 후자를 위해 다음은 다중 경로 다이 st 스트라의 출력을 경로 배열로 전환하는 데 사용 된 코드입니다.

/** 
* 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]); 
    } 
}

출처

2017-05-13 23:38:36 algrithmic

좋아요? (가짜 코드) :

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=[])

출처

2017-05-10 22:47:04 tiwo

다중 경로 Dijkstra에서 경로를 재구성하는 방법은 무엇입니까?

답변

관련 문제