[게임 프로그래머 입문 올인원] 다익스트라 (61강)

A. 다익스트라

1. 다익스트라 알고리즘

a. 다익스트라란?

🌟 그래프 내의 한 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘

 

너비 우선 탐색(BFS)과 유사하지만, 모든 간선의 가중치가 양수일 때에만 사용 가능

각 정점마다 최단 경로를 저장하는 배열을 유지하면서 탐색을 진행

 

b. 알고리즘

1. 초기에는 출발점에서 각 정점까지의 거리를 무한대로 설정하고, 출발점의 거리를 0으로 설정
2. 그런 다음 출발점부터 시작하여 인접한 정점들로의 거리를 갱신하고, 이러한 과정을 반복하여 최단 경로를 찾음

 

👉 즉, 발견한 후보중에 베스트 케이스를 골라서 실행

 

c. 시간복잡도

시간 복잡도는 일반적으로 O(V^2) , V는 정점의 수

우선순위 큐를 사용하여 최소 거리를 갖는 정점을 빠르게 찾을 경우

시간 복잡도를 O((V+E)logV)로 줄일 수 있음, E는 간선의 수

 

d. 문제점

BFS랑 똑같이 목적지의 개념이 없음

모든 부분을 서칭한 상태라서 최적의 알고리즘이 아님

 

 

2. 다익스트라 만들어보기

a. 그래프 만들기

이걸 만들것임

 

정점을 담을 그릇

 

초기값 -1로 설정 / 그래프 생성

 

b. struct 생성

vertex와 cost를 동시에 들고있는 struct를 만들기

 

대소비교하는 부분까지 작성 , const 붙여주기

 

c. 다익스트라 : 생성

push한 부분은 의미없는 정보, 큐의 오류가 생길까봐 작성

 

struct에서 생성한 대소비교에 대한 부분이 없으면 이렇게 오류가 남

 

대소비교를 바꾸려면 값을 음수로 바꾸거나 위와같이 greater로 설정하기

 

d. 다익스트라 : 베스트 케이스 관리

(이 뒤로는 BFS랑 거의 비슷함)

 

지금까지 발견한 최소거리를 넣어주기 = 베스트 케이스 관리

 

int32_max는 엄청 큰 숫자!

 

here점부터 비교해야하니 here로 수정

 

처음 이동 코스트는 0

 

e. 추가정보 관리하기

어떻게 만들었는지 역으로 추적하기 위한 parent 생성

 

parent 생성후 초기화

 

 

f. 실행결과

다익스트라 실행

 

실행결과

 

parent : 3번은 1번에 의해 찾아짐 (베스트케이스)

 

here : 최단거리를 찾아줌

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -