소스 버텍스에서 대상 버텍스까지 모든 최단 경로를 기록하는 방법

Question

현재 부스트 그래프 라이브러리의 dijkstra 알고리즘 http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.html을 사용하여 한 쌍의 버텍스 간의 최단 거리 경로를 계산하고 있습니다. 지금까지 전임 맵에 저장된 최단 경로 하나만 얻을 수 있습니다.

그럼 내 질문은 : 가능한 한 함수가 정점 쌍 사이에 가능한 모든 최단 경로를 반환하도록 할 수 있습니까?

Answer 1

아니요, 직접 제작해야합니다. 한 가지 방법은 Dijkstra에 대한 두 번의 호출을 사용하여 소스 정점 s (G에서)와 싱크 정점 t (즉, 조인 그래프에서 t에서의 거리)까지의 거리를 계산하는 것입니다. 그런 다음 distance (s, u) + distance (u, t) = distance (s, t)와 uv와 같은 노드 u를 정확히 포함하는 부분 그래프를 추출합니다.) + distance (v, t) = distance (s, t) 그리고이 서브 그래프에서 모든 st 경로를 재귀 적으로 열거한다.