[알고리즘] [다익스트라 알고리즘]과 [A* 알고리즘] 그리고 [플로이드와샬 알고리즘]

 

2021.02.03 첫 작성

2021.03.30 수정

 

 

1. 목표점

- 다익스트라는 시작점으로부터 나머지 정점들까지의 최단거리를 구한다.

 - A* 는 시작점이 정해지고, 목표점이 정해지면 두개의 최단 거리를 구한다.

 

2. 남은 거리 고려

- 다익스트라는 시작점에서 정점에 이르는 최단 거리만을 고려. 목적 정점이 없기에 남은 거리를 구할수도 없다.

- A* 는 고려한다.

 

3. 최적 경로 

- 다익스트라는 임의의 시작점으로부터 시작하여 모든 정점을 탐색. 최적 경로 보장 하지 않는다.

(* 이를 해결하기 위해 모든 정점을 시작점으로 가지는 플로이드와샬 알고리즘이다 있다. 하지만 정점의 개수만큼 시간비용이 증가한다.)

- A* 는 시작지점부터 목표지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를 바탕으로 빠른 탐색을 한다. 최적 경로의 근사값을 보장한다.

 

 

뭐가 더 좋은지에 대한건 정답은 없고, 어떤 상황이냐에 따라 사용해지는 알고리즘은 달라질것이다.

예를 들어,

상황 1 .하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우

상황 2. 하나의 정점에서부터 다른 모두의 정점까지 최단 경로를 구하는 경우

상황 3. 하나의 목적지로 가는 모든 최단 경로를 구하는 문제

상황 4. 모든 최단 경로를 구하는 문제

 

상황 1은 A*알고리즘이 적합하다.

상황 2은 다익스트라 알고리즘.

상황 3은 플로이드 워셜 알고리즘

상황 4는 플로이드워셜 알고리즘.

 

그리고 다익스트라 알고리즘에선 음의 가중치를 사용하지 못하나, 플로이드워셜 알고리즘에선 가능하다. 이것또한 차이이다.

 

 

 

 

hyo-ue4study.tistory.com/92

[알고리즘] 길찾기 알고리즘 구현(C++)-(with UE4)

hyo-ue4study.tistory.com/193

[알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm)

hyo-ue4study.tistory.com/323

[알고리즘] 플로이드 와샬(Floyd Warshall) 알고리즘이란? / C++