가중치가 부여 된 그래프에서 두 노드 간의 최단 경로를 찾는 가장 효율적인 (Big O) 알고리즘

Big O 표기법에 따라 가장 효율적인 알고리즘을 찾고 있는데, 비 가중치가 적용된 두 노드 간의 최단 경로를 찾으려고합니다. 유향 그래프.가중치가 부여 된 그래프에서 두 노드 간의 최단 경로를 찾는 가장 효율적인 (Big O) 알고리즘

그래프가 가중치를 사용하면 정상적으로 사용하는 Dijkstra와 힙 우선 검색 사이가 대부분 분리됩니다.

그래프에 가중치가 적용되지 않아 Dijkstra가 BFS보다이 상황에서 사용하기에 덜 효율적입니까? Wikipedia에 따르면

Dijkstra 's와 BFS의 각각의 복잡성을 검색하십시오. –

BFS의 복잡성 - O (E + V)는 실제로 Dijkstra보다 낫습니다. 내가 BFS가이 문제에 대한 최적의 알고리즘인지 아니면 내가 생각하지 못했던 다른 알고리즘이 있는지를 확인하고 싶습니다. 이것은 더 효율적입니다. –

일반적인 경우 단일 가중치, 단일 대상 최적의 최단 경로에 대해 가중치가있는 그래프 (지시 또는 비 방향 여부와 상관없이)에서 우선 검색을 능가 할 수있는 알고리즘은 없습니다.

그러나 예외적 인 추론을 제공 할 수있는 특별한 경우가 있으면 A * 검색을 사용하여보다 효율적인 검색을 구현할 수 있습니다.

2016-10-17 16:21:37

확인해 주셔서 감사합니다. 매우 감사! –

단일 소스 최단 경로

*는 추론에 의존하는 시간 복잡도. 무한 검색 공간의 최악의 경우, 확장 된 노드의 수는 솔루션 깊이 (최단 경로)에서 지수 함수입니다. d : O (b ^d) 여기서 b는 분기 요소 주 당 평균 후임자 수).

가장 적합한 것을 선택하십시오.

2016-10-17 12:46:27

이 목록을 가져 주셔서 감사합니다! BFS가 내가 찾고있는 것 같습니다. –

답변