매우 큰 그래프가 있습니다. 한 꼭짓점에서 다른 꼭지점까지 최단 경로를 찾고 싶습니다. 그래프는 방향이 지정되고 비가 중입니다.최단 경로와 관련한 알고리즘 질문
나는 Dijkstra 알고리즘의 일부 수정을 고려해 봤지만, 일반적으로 가중치가 부여 된 무향 그래프에 사용합니다.
그렇다면 다른 모든 생각은 DFS를 사용하는 것이 었습니다. 모든 가중치를 하나의 것으로 취급 할 수 있기 때문입니다.
제안 사항? a
편집 : 좋아, 나는 BFS, 미안하다고 말하고자했다.
BFS을 사용해보세요.
(다 익스트라의 알고리즘이 가중 유향 그래프에 완벽하게 잘 작동합니다은 - 그냥 비가 중 경우에, 똑똑하게 그 일을하는 것은 폭 우선 검색 본질적으로 같다고 발생합니다.)
나는 이것에 나의 대답의 코멘트를 합병했고 삭제했다; 당신이 좋아하지 않는다면 코멘트를 자유롭게 삭제할 수 있습니다. :-) – ShreevatsaR
A*을 사용해 보셨습니까?
가중치가 적용되지 않은 그래프와 함께 A *를 사용하는 것은 절대적으로 의미가 없습니다 ... 이것은 광범위한 우선 검색보다 나은 것은 아니며 아마도 더 많은 시간이 걸립니다. 당신이 그것을 올바르게하지 않으면, 어떤 경우에는 * 너비 우선 탐색이다). – ShreevatsaR
나는 ShreevatsaR에 동의한다. –
약 노드 수를 가지고 있어요 그리고 얼마나 많은 가장자리? –
DFS를 권장하지 않습니다. http://xkcd.com/761/ – Bolo