그래프 데이터 구조에서 최단 경로를 계산하는 재귀 함수를 작성하는 방법

Question

단일 소스 최단 경로. 지정된 정점이 주어지면 다른 모든 노드에 대한 최단 경로를 계산하십시오. 나는 Dijkstra와 Floyd 알고리즘이 있다는 것을 알고 있습니다. 하지만 그것을 재귀 적으로 해결할 방법이 있다면 생각하고 있습니다. 여기 내 작업은

int RecursiveShortestPath(int s,int t) 
{ 
    int length; 
    int tmp; 
    for (Edge e = G.FirstEdge(s); G.isEdge(s); e = G.NextEdge(e)) 
    { 
     if (ToVertex(e) = t) 
     { 
      length = G.Weight(e); 
      return length; 
     } 
     else if ((tmp = RecursiveShortestPath(ToVertex(e), t)) > 0) 
     { 
      length = length + tmp; 
      return length; 
     } 
    } 
} 

두 인덱스 된 정점 사이의 최단 경로를 계산하고 싶습니다. 재귀를 수행하고 임시 값을 설정하여이 작업을 수행하려고합니다. 한 번 경로가 감지 될 때마다 현재 길이보다 짧은 경우 길이를 계산하고 임시 값을 덮어 쓸 수 있습니다. 문제는 상위 계층으로 반환 될 때 하나의 함수 호출 (여러 하위 분기 경로가있을 수 있음)에 대해 여러 개의 반환 값을 가질 수 있으므로 외부 계층에서 어느 것이 어떤 것인지를 알 수 없으며 엉망으로 끝납니다.

Answer 1

실제 작업을 수행하는 경우 휠을 새로 만들지 않고 Breadth First Search from the boost library을 사용하는 것이 좋습니다.

학교 프로젝트이고 재귀 알고리즘을 구현해야하는 경우 Floyd-Warshall algorithm으로 갈 수 있습니다. 심지어 당신이 아주 쉽게 C++ 코드로 변환 할 수있는 의사 코드가 있습니다.