-1
나는 Dijkstra의 알고리즘이 어떻게 작동하는지 알며 시간 O (m + n log n) 시간에 실행되도록 만들 수 있음을 알고 있습니다. 어떻게하면 단일 소스 최단 경로에 대한 알고리즘이 이보다 나은 지 어떻게 알 수 있습니까?Dijkstra의 알고리즘이 최상의 단일 소스 최단 경로 알고리즘이라는 것을 어떻게 알 수 있습니까?
A
답변
1
Dijkstra의 알고리즘은 사실 그래프에서 단일 소스 최단 경로를 계산하는 데있어 반드시 가장 빠른 알고리즘이 아닙니다. 예를 들어, 모든 에지가 정수 가중치를 갖고 기계어가 이러한 정수를 보유 할만큼 충분히 크다고 가정하면 Thorup에서 개발 한 시간 O (m + n)에 실행되는 알고리즘을 사용할 수 있습니다. Dijkstra 알고리즘보다 점근 적으로 빠릅니다. 가중치가없는 경우 또는 모든 가중치가 동일한 경우 간단한 BFS가 O (m + n) 시간에이를 수행합니다.
Dijkstra의 알고리즘을 이보다 더 빨리 구현할 수 없다는 것을 어떻게 알 수 있습니까? " 또는 "비 음의 에지 가중치가있는 그래프에 대해 가능한 가장 빠른 단일 소스 최단 경로 알고리즘입니다." – templatetypedef
이것이 음이 아닌 가중치를 가진 그래프에 대해 가능한 가장 빠른 단일 소스 최단 경로 알고리즘이라는 것을 어떻게 알 수 있습니까? – AdamSMith