프로그래밍 콘테스트에 가장 적합한 단일 소스 최단 경로 알고리즘은 무엇입니까?

Question

나는 UVa 문제 세트에서 this graph problem을 연구 중이었습니다. 이는 음의 에지 가중치가없는 단일 소스 최단 경로 문제입니다. 필자가 수집 한 것으로부터, 이러한 문제에 대한 가장 좋은 실행 시간을 가진 알고리즘은 우선 순위 큐로 피보나치 힙을 가진 Dijkstra입니다. 실제로는 바이너리 힙이 구현하기 쉽고 꽤 잘 작동합니다.

그러나 바이너리 힙조차도 꽤 많은 시간이 걸리고 경쟁 시간에는 제한이있는 것으로 보입니다. STL이 일부 힙 알고리즘과 우선 순위 대기열을 제공하지만 Dijkstra가 필요로하는 감소 키 기능을 제공하지 않는 것으로 알고 있습니다. 아니면 내가 틀린거야?

다른 가능성은 단순히 Dijkstra 's를 사용하지 않는 것입니다. This forum thread에는 위의 문제를 광범위한 우선 검색/Bellman-Ford로 해결했다고 주장하는 사람들이 있습니다. 코드 작성이 훨씬 쉽습니다. (편집 : OTOH, 우선 순위 대기열에 대한 분류되지 않은 배열을 가진 Dijkstra 's.) BFS/Bellman-Ford는 입력 크기가 상당히 크다고 생각하여 조금 놀랐습니다. 나는 다른 문제가 다른 복잡성의 해결책을 요구할 것이라고 생각하지만, 나의 질문은, 얼마나 자주 그러한 대회에서 Dijkstra를 사용해야 할 것인가? 대신 간단하지만 느린 알고리즘에 대해 더 연습해야합니까?

Answer 1

필자 자신의 경험에 비추어 볼 때, 프로그래밍 경연 대회에서 힙을 사용하여 Dijkstra 알고리즘을 구현할 필요가 전혀 없습니다. 더 느리지 만 효율적인 알고리즘을 사용하면 대부분의 시간을 낭비 할 수 있습니다. 다른 Dijkstra 구현을 사용하여 다른/더 간단한 알고리즘을 기대하는 문제를 해결할 수도 있지만, 드문 경우입니다.

Answer 2

Boost Graph Library에는 Dijkstra와 Bellman-Ford에 대한 구현이있는 것으로 보입니다.

Answer 3

당신이 좋은 가장 먼저 추론 가지고 올 수 있다면, 내가 A*

Answer 4

익스트라를 사용하려고 할 것이다 간단한 우선 순위 큐도 대규모 데이터 세트를 위해 잘해야한다. 연습을하고 있다면 바이너리 힙으로 시도해보고 성능을 비교할 수 있습니다. 물론, 나는 fibonacci heap을 수행하는 것이 약간의 프린지이며, 다른 데이터 구조와 알고리즘을 먼저 연습하도록 선택할 것이라고 생각합니다.

흥미롭게도 우선 순위 대기열을 사용하는 것은 현재 최고의 솔루션을 먼저 탐구하는 휴리스틱 스 (breadth-first search)와 동일합니다.

Answer 5

O ((E + V) log V)에서 감소 키없이 힙/우선 순위 대기열을 사용하여 Dijkstra를 구현할 수 있습니다. 키를 줄이려면 우선 순위 대기열에 새 항목을 추가하고 (대기열에 남아있는 항목은 그대로 둡니다) 거리를 사용하여 배열을 업데이트하십시오. 우선 큐에서 최소 요소를 가져 와서 거리 배열과 동일한 지 확인하십시오. 그렇지 않으면 감소시키려는 키이므로 무시하십시오.