최단경로 탐색 알고리즘 비교

개요

 학기 중에 DFS를 사용하여 주어진 미로의 최단 경로를 탐색하는 과제를 한 적이 있었다. 그리고 학기의 마지막 즈음에 다익스트라 알고리즘으로 그래프의 최단 경로를 탐색하는 것도 구현했었다. 그러다가 든 의문이 "다익스트라 알고리즘이 그래프에서 최단거리를 찾을 수 있다면 미로에서도 찾을 수 있을까?"였다. 이번 글에서는 여러 최단 경로 탐색 알고리즘으로 미로의 최단 경로를 구하고 알고리즘들을 비교해볼 것이다.

 모든 코드는 Clion을 사용해 C++로 작성되었으며 개발환경은 macOS Big Sur 11.4 이고, 실행 환경은 라즈베리파이 OS와 g++ 8.3이 설치된 라즈베리파이 4B이다.

미로와 다익스트라

 다익스트라는 기본적으로 "음이 아닌 가중치를 가진 간선들과 정점들로 구성된 그래프"에서 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 탐색하는 알고리즘이다. 이 알고리즘의 의사코드는 다음과 같다.

function Dijkstra(Graph, Source):

     //Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.

      while Q is not empty:                      // Q 집합이 공집합 아닐 경우, 루프 안으로!
          u ← vertex in Q with min dist[u]    // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
          remove u from Q                         // U 노드를 방문한 것이므로 Q집합에서 제거

          for each neighbor v of u:           // U의 이웃노드들과의 거리 측정
              alt ← dist[u] + length(u, v)      // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
                                                             //= source to U + V to U = source to U
             if alt < dist[v]:               // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
                 dist[v] ← alt            //  V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
                  prev[v] ← u            // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈

     return dist[], prev[]       //계산된 거리값과 목적지를 리턴

 이 알고리즘에서 가장 핵심적인 부분은 지금까지 최단 경로를 찾은 정점들의 집합과 인접한 정점들 중 가장 가까운 정점를 찾는 부분이다. 다익스트라 알고리즘에서 "찾은 정점들의 집합"은 결국 이 과정을 반복하면서 한 개씩 증가하기 때문이다. 따라서 이 부분의 성능을 향상시키는 것이 전체 알고리즘의 성능을 향상시킬 것이라 예상할 수 있다.

 미로를 그래프로 표현하고 저장하는 논리와 방법은 미로의 자료구조에서 확인할 수 있다. 우리가 일반적으로 보는 미로는 모든 통로에 가중치가 없거나 같은(결과적으로 없는 것과 다를바 없다) 그래프라고 할 수 있다. 모든 칸은 정점이며 인접한 칸으로 가는 열린 통로는 간선, 닫힌 벽은 존재하지 않는 간선 또는 무한한 가중치를 가진 간선이다. 다익스트라 알고리즘은 이런 일반적인 미로에서도 충분히 빠르게 최단거리를 찾을 수 있다. 하지만 후에 비교를 위해 무작위적인 가중치를 가진 미로 또한 구현하였다.

알고리즘의 테스트 환경은 다음과 같이 정의하였다.

• 간선들은 모두 같은 가중치, 또는 무작위적인 가중치를 가질 것.
• 미로의 막힌 벽은 무한한 가중치를 갖는 간선으로 표현할 것.
• 따라서 미로의 모든 칸(정점)들은 상, 하, 좌, 우로 인접한 네 개의 칸들과 간선으로 이어져 있을 것.
• 단, 네 모서리의 칸들은 더 이상 갈 수 없는 곳을 미로의 한계로서 표시함.

A* 알고리즘

 A* 알고리즘은 간단히 말해 다익스트라 알고리즘의 확장이라고 할 수 있다. 다익스트라 알고리즘은 완전히 개방된 미로와 같은 환경에서 성능이 BFS와 다를 바 없어진다. 만약 모든 간선의 가중치가 같거나 비슷하고, 벽이 존재하지 않는 미로가 있다고 생각해보자. 최단 경로는 단지 시작점에서 도착점까지 쭉 일자로 이으면 될 것이다. 하지만 다익스트라 알고리즘은 마치 BFS처럼 인접한 정점들을 하나씩 방문하며 아주 단순하게 해결할 수 있는 문제에서 불필요하게 많은 정점을 방문하게 될 것이다.

 A* 알고리즘은 이를 보완하는 알고리즘이다. 다익스트라 알고리즘은 새 정점을 방문하고자 할 때 시작점부터 해당 정점까지의 거리만을 고려한다. 만약 해당 정점부터 도착점까지의 거리 또한 고려할 수 있다면 어떨까? 시작점에서 가깝기도 하지만 동시에 도착점에도 가까운 정점을 방문할 수 있다면 위에서 언급한 벽이 없는 미로와 같은 환경에서 더 나은 성능을 보여줄 수 있을 것이다. 왜냐하면 도착지에서 너무 먼 정점들은 시작점에서 가깝더라도 더 후순위에 고려할 것이기 때문이다.

 이를 구현하기 위해서는 특정 정점에서부터 도착점까지의 거리를 올바르게 추정할 수 있어야 한다. 추정치는 해당 정점의 우선순위를 결정하는데 영향을 미칠 것이다. 만약 추정치가 실제 거리보다 길다면 알고리즘은 해당 정점이 실제보다 더 멀다고 생각할 것이며, 실제로는 도착점에 가까움에도 불구하고 방문 후순위로 밀릴 것이다. 그리고 결국 알고리즘은 최단 경로로 도착점에 도달하지 못할 것이다. 따라서 도착점까지의 거리를 추정하는 휴리스틱 함수는 항상 실제 거리보다 짧은 거리로 추정해야한다.

 A* 알고리즘을 조금 더 구체적으로 살펴보자. 결국 다익스트라 알고리즘과 다른 점은 인접 정점의 평가 방식이 추가되었다는 것이다.

 인접 정점 n의 방문 순위를 결정하는 값을 f(n), 정점 n까지의 비용을 g(n), 정점n에서 도착점까지의 비용을 h(n)이라 할 때, 다음과 같은 식으로 이를 나타낼 수 있다.

$$f(n) = g(n) + h(n)$$

다익스트라에서 인접 정점을 시작점에서부터의 거리로 줄 세웠다면, A*는 그 값에 도착점까지의 거리를 더하여 줄 세운다고 보면 된다. 이 테스트를 위해 어떠한 방식으로 휴리스틱 함수를 만들었으며 거기에 어떤 문제가 있었는지, 그리고 이를 어떻게 해결했는지는 아래에 후술한다.

휴리스틱

A* 알고리즘을 테스트하던 중 결과를 관찰하면서 중요한 오류가 발생했음을 알게되었다.

위는 모든 알고리즘이 모든 가중치가 같은 200x200 미로에서 최단 경로를 탐색한 결과이다. 모든 최단 경로의 거리가 같은 것을 볼 수 있다. 가중치가 모두 같을 때는 올바르게 동작하고 있다.

 위는 정규분포의 가중치를 갖는 200x200 미로의 결과이다. 보다시피 일부 A* 시행에서 최단 경로가 아닌 경로를 최단 경로로 출력한 것을 볼 수 있다. A* 알고리즘이 어떻게 특정 정점과 도착점까지의 거리를 추정하느냐에서 이 문제의 이유를 찾을 수 있었다.

 미로에서는 대각선으로 이동할 수 없으므로 유클리드 거리로 추정하는 것이 올바르지 않다. 그것보다는 정확한 추정을 위해 맨하탄 거리를 사용하는 것이 옳다. 이 경우에도 도착점까지의 거리 추정치는 맨하탄 거리를 기반으로 했는데 여기서 문제가 발생한 것이다.

 모든 간선의 가중치가 같다면 도착지까지의 거리 추정을 쉽게 할 수 있다. 맨하탄 거리에 가중치를 곱하면 되는 것이다. 하지만 간선의 가중치가 무작위라면 어떻게 추정할 것인가? 위 결과는 맨하탄 거리에 모든 가중치의 평균을 곱하는 형식으로 추정치를 구했을 때 나타난 결과이다. 거리가 많이 남았다면 크게 문제되지 않겠지만, 가까워질수록 남은 거리가 추정치보다 작아질 가능성이 올라간다. 만약 실제 남은 거리가 추정치보다 작아진다면 알고리즘은 그 경로를 올바르지 않은 경로로 판단할 것이다. 

 다시 말해, 하한이 없는 가중치가 무작위적으로 존재한다면 평균을 기반으로 한 맨하탄 거리 추정 함수는 용인되지 않는다는 것이다. A*에서 휴리스틱 함수는 항상 실제 거리보다 작은 거리로 추정해야 하는데, 가중치의 하한이 정의되지 않는다면 언제든 휴리스틱 추정치보다 짧은 실제 거리가 발생할 수 있기 때문이다.

 올바른 휴리스틱 추정치를 위해서는 무작위적인 가중치의 하한을 정의하고 이를 기반으로 맨하탄 거리를 계산해야 했다. 이렇게 하니 올바른 휴리스틱 추정을 할 수 있었고 항상 최단 경로를 찾을 수 있었다. 하지만 휴리스틱 추정치가 해당 정점까지의 비용에 비해 이전보다 더 적어지는 바람에 A* 알고리즘은 더 많은 노드를 방문해야 했으며, 수행시간이 늘어나게 되었다. 탐색이 정확해진 대신에 비용이 증가한 것이다.

최단경로 탐색 알고리즘의 자료구조

 순수한 다익스트라 알고리즘은 O(n^2)의 시간 복잡도를 갖는다고 알려져 있다. 모든 정점에 대하여, 한 정점을 찾을 때마다 가장 작은 가중치를 갖는 간선을 찾아야한다. 순차탐색을 사용한다면, 모든 인접한 정점에 대해 탐색해야 할 것이며, 따라서 O(n^2)의 복잡도를 갖게 되는 것이다.

결과로서 보겠지만, 많은 복잡한 경우에 순수한 다익스트라 알고리즘은 그렇게 좋은 성능을 발휘하지 못한다. 그 이유는 가장 작은 가중치를 갖는 간선을 찾는 과정 때문인데, 이 부분에서 순진하게 선형 탐색을 한다면 이 부분이 전체 O(n^2)에서 한 n을 차지하지 때문이다. 다른 쪽은 모든 정점을 하나씩 찾은 정점 집합에 넣는 부분이라 단축할 수 없지만 최소 비용 간선을 찾는 과정은 분명 복잡도를 감소시킬 방법이 존재한다.

BORIS V. CHERKASSKY의 SHORTEST PATHS ALGORITHMS: THEORY AND EXPERIMENTAL EVALUATION(1993)에서는 최소 비용 간선 탐색을 위해 R-힙, 피보나치 힙, 이중 버켓 자료구조 등을 사용해 최소 비용 인접 간선을 탐색하는 것을 보여준다. 본 프로젝트에서는 다음 두 개의 큐 자료구조를 구현하여 사용하였다.

• 우선순위 큐
• 버킷 큐

STL 우선순위 큐

우선순위 큐는 STL의 에 있는 std::priority_queue<>를 사용하였다. 다음 두 사진은 Apple clang 12.0.5 와 g++ 8.3.0 에서의 std::priority_queue<>의 선언이다.

STL의 priority_queue(이하 PQ)는 어뎁터로서 underlying container를 필요로 하고 기본적으로 vector를 쓰고 있는 것을 볼 수 있다. 아래에서 보다시피 C++ 표준은 이 컨테이너가 front(), push_back(), pop_back() 함수들을 지원하고 임의 접근 이터레이터를 지원할 것을 요구한다.

직접 컨테이너를 만들 것이 아니기 때문에 기본값인 vector를 그대로 썼다.

PQ에서 들어온 모든 데이터들은 주어진 비교 함수를 사용하여 이진 힙으로 정렬된다. 기본 비교 함수는 가장 큰 요소를 맨 앞으로 유지하도록 되어있다. 가중치를 음수로 저장하면 가장 작은 가중치가 음수 형태로 맨 앞으로 오게되므로 이 역시 그대로 사용하였다.

버킷 큐

버킷 큐는 STL에 구현되어 있지 않으므로 직접 구현하였다. 속도와 편의를 각 키에 해당하는 버킷은 한 개의 백터로, 그리고 그 전체는 백터의 배열로 구현하였다.

해시맵과 같은 자료구조에서는 들어오는 값의 키를 해싱하여 그 값에 해당하는 키를 가진 버킷에 들어오는 값을 넣는 구조이다. 마찬가지로 버킷 큐는 들어로는 값의 키를 어떠한 방식으로 처리하여 해당하는 버킷에 넣는다. 그리고 큐에서 가장 우선순위가 빠른 원소를 빼낼 때는 비어있지 않은 버킷 중 가장 앞에 있는 버킷에 한 원소를 빼낸다. 공간을 적게 차지하려면 들어오는 키를 다루는 방식을 교묘하게 구현해야 하겠지만 현재로서는 단순히 정수 가중치값을 갖는 버킷으로 바로 접근하도록 하였다.

버킷 큐에서 성능 하락을 일으키는 가장 큰 요인은 크기가 1 이상인 버킷 중 가장 작은 키 값을 갖는 버킷을 탐색하는 과정이다. 모든 간선의 가중치가 10인 200 x 200 크기의 미로에서 정점이 가질 수 있는 최대 거리(출발점부터의 가중치 합)는 대략 4400에 수렴하는 경향을 보였다. 최대 거리가 4400인 정점 하나만 들어가 있는 최악의 경우, 0 부터 4400 까지 의미없는 조건문을 반복한 후에야 최소 키 값을 갖는 정점을 찾을 수 있다는 말이 된다.

버킷에 새로운 정점이 들어올 때마다 그 키 값이 지금까지 알고있는 최소 키 값보다 작은지 확인하고 만약 작다면 최소 키 값을 그 키 값을 갱신하도록 하였다. 그리고 최소 키 값부터 선형 탐색을 하면 0부터 탐색하는 것보다 훨씬 빠르게 최소 키 값을 갖는 크기가 0이 아닌 버킷을 찾을 수 있다. 이를 통해 버킷 큐를 사용하는 최단 경로 탐색 알고리즘의 실행 시간을 극적으로 단축시킬 수 있었다. 구현 정의 상 선형 탐색이지만, 큐에 들어가 있는 대부분의 정점들이 단계에 따라 특정 키 값 주변에 모여있고 방금 전에 정점이 제거된 버킷에서부터 뒤로 탐색해나가는 과정을 고려하면 '거의' 상수시간에 가까운 탐색을 할 수 있었다. 이 과정이 없다면 최소 키 값에 대한 선형시간의 탐색이 필요하지만 말이다.

STL 우선순위 큐와 버킷 큐

PQ는 자료를 힙으로서 구성하고 버킷 큐는 버킷으로 구성한다. 우선순위 힙 큐는 삽입과 삭제에 힙을 만드는 과정이 수반된다. 따라서 전체 원소 개수 n에 대하여 삽입과 삭제에 모두 O(log n)의 복잡도를 갖는다. 반대로 버킷 큐는 키 값을 사용하여 버킷에 바로 접근하므로 삽입에 상수 시간을 사용한다. 삭제의 경우 순수하게 0번 버킷부터 체크한다면 O(n)의 시간 복잡도를 갖겠지만 위에서 소개했다시피 최단 경로 탐색 알고리즘의 특성에 따라 상수 시간에 충분히 가까운 만큼 빠르게 삭제할 수 있다.

따라서 다른 모든 과정이 동일하거나 비슷한 복잡도를 갖는다면 PQ보다 버킷 큐를 사용하는 최단 경로 탐색 알고리즘이 더 빠를 것이 자명하다. 뒤에 보일 결과 또한 이를 지지하였다.

테스트

테스트는 다음과 같은 4개의 환경에서 진행하였다. 각 미로는 총 100번 새로 생성하여 생성할 때마다 모든 알고리즘이 최단 경로를 탐색하도록 하였다. 이후 각 알고리즘의 수행시간을 비교하였다.

• 모든 가중치가 같은 50x50 미로
• 정규분포를 보이는 무작위 가중치를 갖는 50x50 미로
• 모든 가중치가 같은 200x200 미로
• 정규분포를 보이는 무작위 가중치를 갖는 200x200 미로

미로는 Eller's algorithm을 사용하여 생성하였기 때문에 충분히 빠른 시간 내에 생성할 수 있었다. 테스트한 알고리즘의 종류는 다음과 같다.

• 순진한 다익스트라 알고리즘(이하 DIK)
• 우선순위 큐를 사용하는 다익스트라 알고리즘(이하 DIKPQ)
• 버킷 큐를 사용하는 다익스트라 알고리즘(이하 DIKBQ)
• 우선순위 큐를 사용하는 A* 알고리즘(이하 ASPQ)
• 버킷 큐를 사용하는 A* 알고리즘(이하 ASBQ)

DIK는 가장 짧은 간선을 탐색할 때마다 인접한 간선 집합을 단순히 선형 탐색하는 알고리즘이다.

다음은 다섯 개의 알고리즘을 위의 네 환경에서 테스트한 결과이다. 아래 네 그래프의 y축은 로그스케일이다.

• 모든 가중치가 같은 50x50 미로
• 정규분포를 보이는 무작위 가중치를 갖는 50x50 미로
•  
• 
• 모든 가중치가 같은 200x200 미로
• 
• 정규분포를 보이는 무작위 가중치를 갖는 200x200 미로
• 

전체적으로 봤을 때 단순한 선형 탐색을 하는 DIK은 비교적 성능이 좋지 않으며 미로의 크기가 커질 수록 더 나쁜 성능을 보인다. O(n log n)의 복잡도를 갖는 다른 알고리즘보다 O(n^2)를 갖는 DIK이 훨씬 나쁜 성능을 보이는 것은 예견된 사실이다. 이번에는 DIK를 제외한 다른 알고리즘들만을 비교해 보았다. 이번에는 모든 그래프의 y축을 로그스케일이 아닌 일정한 비율로 설정하였다.

• 모든 가중치가 같은 50x50 미로
• 
• 정규분포를 보이는 무작위 가중치를 갖는 50x50 미로
• 
• 모든 가중치가 같은 200x200 미로
• 
• 정규분포를 보이는 무작위 가중치를 갖는 200x200 미로
• 

결과 해석

위 그래프들을 종합해보면 다음과 같은 사항들을 특기할 수 있다.

1. 수행시간의 평균을 생각했을 때 ASBQ < DIKBQ < ASPQ < DIKPQ < DIK 순으로 수행시간이 적은 것을 알 수 있다.
2. 다익스트라 알고리즘들은 수행시간이 비교적 일정한데 비해 A* 알고리즘들은 수행시간이 더 들쭉날쭉하다.
3. A* 알고리즘들은 서로 비슷한 수행시간의 변동을 보인다.
4. ASPQ의 경우 일부 시행에서 오히려 가장 성능이 안좋을 때도 있다.
5. 반면 ASBQ는 항상 모든 알고리즘보다 빠르다.
6. 미로가 커질수록 가중치의 변화가 수행시간에 미치는 영향이 적어진다.

수행시간의 차이부터 살펴보자면, 다익스트라와 A* 간의 성능 차이보다 우선순위 큐와 버킷 큐의 성능 차이가 수행시간에 더 많은 영향을 미친 것으로 보인다. 평균 값으로 비교했을 때 ASPQ보다 DIKBQ가 더 수행시간이 짧은 것이 그 이유이다.

다익스트라 알고리즘의 수행시간은 일정한 반면 A* 알고리즘의 수행시간이 더 요동치는 것도 특이한 점이다. 이는 모든 인접한 정점에 [출발점부터 해당 정점까지의 거리]와 [해당 정점에서부터 도착점까지의 거리 추정치]를 더하여 그 중 가장 작은 값을 갖는 정점을 찾아 방문하는 A* 특성상 나타난 결과라고 보인다. 다익스트라는 무조건 출발지부터의 거리가 짧은 정점부터 방문하는데 비해 A*는 도착지까지의 거리 또한 짧은 정점부터 방문한다. 하지만 무작위로 생성된 미로라는 환경 특성상 어느 범위를 아주 벗어나는 정점들을 제외하는 것에만 의의가 있고, 따라서 일정한 성능을 내지 않는다고 볼 수 있다.

결과가 말하고 있다시피 다익스트라는 최단 경로일 가능성이 매우 적은 일정 범위 밖의 정점들을 탐색하느라 시간을 소모하는 것으로 보인다. 그에 비해 A*는 일정 범위 바깥의 정점은 거의 탐색하지 않는 대신, 도착지까지의 거리가 짧다고 판단되면 설령 그곳이 최단 경로가 아닐지라도 우선 탐색한다. 이 과정에서 우연하게 그곳이 최단 경로와 가깝다면 극적인 수행시간의 단축이 수반되고, 그렇지 않다면 오히려 늘어날 수 있는 것이다. 이는 자료구조의 문제라기보다는 알고리즘 자체의 특징이며 2번과 3번, 4번 사항을 설명한다.

A* 알고리즘의 이런 특징에도 불구하고 자료구조를 우선순위 큐에서 버킷 큐로 바꾸는 것은 수행시간을 극적으로 단축시킨다. 위에서 설명했다시피 여기서 사용한 버킷 큐는 인접한 정점들의 거리가 서로 비슷하다는 문제의 특징에 따라 시간 복잡도를 상수 시간에 가깝게 단축시킬 수 있었다. 이에 각 알고리즘의 수행시간은 작게는 두 배에서부터 크게는 다섯 배까지 차이났다. 1번과 5번 사항은 이런 이유로 나타났다.

테스트 환경은 크게 두 개였는데, [정규분포를 보이는 무작위 정수 가중치 미로]와 [일정한 가중치 미로]가 그것이다. 다익스트라 알고리즘은 일반적인 그래프에서 가중치가 모두 같을 때 더 나쁜 성능을 보일 것으로 예상되었다. 모든 가중치가 같다면 최소 비용 간선을 우선 방문하는 다익스트라의 특징이 사라지고 BFS와 다를 바 없어지기 때문이다. 때문에 미로에서 이 가중치를 다르게 주었을 때 다익스트라 알고리즘의 성능에 차이가 있는지 알아보려 한 것이다.

하지만 놀랍게도 가중치가 무작위적이었을 때보다 모두 같았을 때 수행시간이 더 짧았다. 이에 대한 이유로는 다음을 들 수 있다.

1. 최단 경로를 결정하는 가장 큰 요소는 간선의 가중치가 아니라 미로의 닫힌 벽이었다.
2. 미로 특성상 각 정점은 인접한 네 개의 정점에게만 연결되어 있었다.
3. 미로가 비교적 컸다.

미로에서 최단 경로를 결정하는 가장 큰 요소는 간선의 가중치라기 보다는 '해당 정점까지 가려면 얼마나 긴 경로(=정점의 방문)가 필요한가'였다. 간선 가중치의 평균은 10인데 반해 출발지부터의 거리는 그것을 훨씬 넘기 때문이다. 또한 미로 특성상 출발지부터 도착지까지의 경로 자체가 그렇게 많지 않다. 이는 위의 2번 사항 때문인데, 각 정점이 인접한 정점들과만 연결되어있기 때문에 일반적인 그래프에 비해 그렇게 많은 경로를 기대하기 어렵다.

미로의 크기가 비교적 큰 것도 영향을 주었다. 미로가 커지면 커질수록, 새로운 정점에 대한 거리에 하나의 간선 가중치가 차지하는 비중이 줄어든다. 따라서 최소 비용 정점을 찾는 과정에서 인접한 정점들까지의 비용은 인접한 간선의 비용보다 출발지에서부터 거리가 결정하게 된다. 따라서 무작위적 가중치는 정점들의 비용을 파편화시켜 탐색하기 어렵게 만들 뿐 정작 성능에 도움이 되지 않았다. 오히려 모든 가중치가 같아 정점들의 비용이 비슷한 곳에 몰려있는 경우 더 빠른 탐색이 가능했다.

미로의 크기가 커질수록 가중치 하나의 영향이 작아지고, 가중치의 무작위적 변화 역시 영향이 작아졌다. 위 그래프에서 보다시피 미로가 커질수록 가중치 변화에 따른 수행시간 차이가 적어지는 것도 그 이유라고 볼 수 있겠다.

결과 요약

1. 미로에서 최단 경로를 찾는 환경에서, 알고리즘의 차이도 유의미하지만 자료구조의 차이 또한 중요하다.
2. A* 알고리즘은 휴리스틱 평가가 포함되기 때문에 수행시간의 변동이 있지만, 다익스트라 알고리즘은 그렇지 않다.
3. A* 알고리즘에서 올바른 휴리스틱 함수를 만들지 않으면 최단 경로를 보장할 수 없다.
4. 그럼에도 불구하고 휴리스틱 함수를 올바르게 만들었다면 다익스트라 알고리즘보다 A* 알고리즘이 더 빠르다.
5. 테스트한 알고리즘 중에서 미로찾기 알고리즘으로서 가장 빠른 것은 버킷 큐를 사용한 A* 알고리즘이었다.

참고

Github 링크