관리 메뉴

기억을 위한 기록들

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

자 & 알/알고리즘

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

에드윈H 2021. 3. 30. 17:28

 

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)

2020-08-28 첫작성 2021-02-03 1차 수정 언리얼엔진을 이용하여 구현해보았고, 위젯버튼만 블루프린트 사용. 우선순위 큐 기반(TArray 사용)으로 작성. 간단설명: 마우스 왼쪽버튼으로 시작지점을 선택,

hyo-ue4study.tistory.com

hyo-ue4study.tistory.com/193

 

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

다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로

hyo-ue4study.tistory.com

hyo-ue4study.tistory.com/323

 

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

hyo-ue4study.tistory.com/193 [알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길

hyo-ue4study.tistory.com