2
내 그래프에 꼭지점을 연결하는 가장자리가 없습니다. 두 꼭지점 사이에 하나의 모서리 만 있습니다. Wikipedia에서 주어진 조건에 따라 최단 경로를 계산하는 데 사용되는 알고리즘에 대해 알아야합니다. 가장 유명한 알고리즘 중 하나는 Dijkstra's algorithm입니다.이 알고리즘은 소스 버텍스에서 그래프의 다른 모든 버텍스까지 최단 경로를 찾습니다.
그러나 Dijkstra's algorithm을 사용하면 불필요한 모든 정점을 탐색 할 수 있지만 내 목표는 단일 소스에서 단일 대상까지 최단 경로를 찾는 것입니다. 어떤 전략을 사용해야합니까? 그래서 다른 모든 정점을 탐색 할 필요가 없습니다.그래프에서 단일 소스에서 단일 대상까지의 최단 경로
내 접근 방식 중 하나는 bidirectional bfs을 사용하는 것입니다. bidirectional bfs 나는 두 개의 bfs을 source node에서, 다른 하나는 destination node에서 적용하는 것을 의미합니다. 같은 시간에 두 번 모두 같은 것을 발견하면 처음으로 bfs을 종료 할 수 있습니다. 소스에서 자식까지의 경로 union은 자식에서 대상까지 경로가 원본에서 대상까지의 최단 경로가됩니다.
위키 피 디아와 bidirectional bfs에 설명 된 모든 접근법 중에서 어느 것이 내 그래프에 가장 적합한가?
주어진 정점 u 및 v에 대한 v-u에서 최단 경로 찾기 : 581이 소개 알고리즘 (CLRS) 두 번째 버전 페이지에
관련 : http://stackoverflow.com/questions/2655880/how-to-optimize-dijkstra-algorithm-for-a-single-shortest-path-between-2-nodes –
@KshitijMehta : 내가해야 하는가 [Dijkstra의 알고리즘] (http://stackoverflow.com/questions/2655880/how-to-optimize-dijkstra-algorithm-for-a-single-shortest-path-between-2-nodes)을 여기에 적용 하시겠습니까? 이것이 내 그래프를위한 최선의 방법인가? –
A * 검색을 사용할 수도 있지만 휴리스틱 함수를 사용하는 것이고 "인공 지능"기반 접근 방식에 가깝습니다. 그것 이외에, Dijkstra의 것이 최선의 선택입니다. –