그래프에서 위치를 찾기 위해 폭 넓은 첫 번째 검색을 사용하고 있습니다. 알고리즘이 올바르게 작동한다고 확신하지만 끝나면 결과에 가장 짧은 경로를 찾는 데 어려움을 겪고 있습니다. 기본적으로 BFS를 사용하여 시작 위치에서 최종 위치까지 이동할 수 있지만 끝에서 시작까지 최단 경로를 구성하는 방법을 알지 못합니다. 어떤 도움을 주시면 감사하겠습니다.폭 넓은 첫 번째 검색에서 어떻게 최단 경로를 신속하게 찾으십니까?
감사합니다.
하나의 옵션은 다음과 같습니다. 각 노드를 "상위"노드 (아마도 해시 테이블 또는 노드를 나타내는 모든 유형에 "상위"필드 추가)와 연관시키는 일종의 방법을 만듭니다. 그런 다음 대기열에서 노드 u를 dequeue하고 노드 v를 대기열에 추가 할 때마다 v의 부모 포인터를 노드 u로 설정합니다. 이것은 노드 v에 도달하는 방법이 u에 대한 경로를 따라 한 다음 v에 도달하도록 한쪽 가장자리로 경로를 연장하는 것입니다.
일단이 작업을 완료하고 BFS를 끝내면 목적지 노드로 시작하여 최단 경로를 역순으로 한 다음 시작 노드에 다시 도착할 때까지 부모 포인터를 반복적으로 따르십시오. 일단이 경로를 사용하면이 경로를 역으로 바꿔 실제 최단 경로를 얻을 수 있습니다.
희망이 도움이됩니다.
이것은 최단 경로가 초기 BFS에서 거꾸로 따라가는 것을 전제로하고 있으며 이는 일반적으로 사실이 아닙니다. – congusbongus
@ CongXu- 확실히. 나는 OP가 처음부터 BFS를 사용하고 있었기 때문에 그래프가 비 가중치를 가졌기 때문에 BFS는 소스 노드에서 각 대상 노드까지 최단 경로를 찾는다 고 가정했습니다. 가중치 그래프에서는 다른 알고리즘 (Dijkstra, Bellman-Ford 등)을 사용합니다. – templatetypedef
+1 뛰어난 대답입니다. 방문한 노드를 'null'로 표시하고 부모 노드를 방문한 노드를 방문 할 수 있습니까? (BFS에서는 노드를 표시해야합니다. 그렇지 않습니다. 녹슨 해요.) – Patrick87
두 점 사이의 최단 경로 찾기는 실제로 점을 찾는 문제를 포함하므로 이미 작동중인 BFS가 있다는 사실은 최단 경로 문제에 더 가깝지 않습니다. A *, Dijkstra, Bellman-Ford와 같은 최단 경로 알고리즘에 대한 여러 옵션이 있으므로 잘 확인하십시오. – congusbongus
나는 OP가 그래프가 가중치가 없다고 가정하고 있다고 생각합니다. – templatetypedef
@Bob John, 그래프의 가중치 및/또는 지시 여부를 지정해야합니다. 그렇지 않은 경우 BFS를 역 추적하면 해결 방법이 제공됩니다. 최대 길이가 같은 최단 경로가 여러 개있을 수 있습니다. – Adam