다익스트라

첫 번째 궁금증, what?

다익스트라 알고리즘이 무엇인가?

 

다익스트라란, 그래프의 한 정점에서 모든 정점으로 이동하는 각 경우당 가장 효율적인 방법을 찾아내는 알고리즘이다.

 

- 비용이 주어질 때 비용을 최소화하여 움직일 수 있는 방법을 찾아내는 알고리즘이다.

- 비용으로 시간 및 돈 등을 들 수 있다.

- 시작지점에서 최소 비용으로 갈 수 있는 정점을 구하고, 정점에서부터 목표지점으로 가는 경로의 비용을 더하여 나온 cost가 정점을 지나지 않고 목표지점으로 갈 경우의 cost와 비교하여 적은 것을 선택한다.

---

두 번째 궁금증, why?

다익스트라가 왜 필요한가?

가장 "적은" 비용으로 가장 "효율적(빠른)"방법을 찾아내는 알고리즘이기에, 실생활에서 적극적으로 사용이 가능하다.

 

예) 네비게이션 상의 시작점에서 도착점으로 가기 위한 효율적인 방법을 찾기 위해, 최소비용 최고효율을 찾아주는 알고리즘인 다익스트라를 사용할 수 있다.

---

 

세 번째 궁금증, how?

어떻게 사용할 수 있을까?

 

<필수요소>

- 인접행렬을 구현

단방향 혹은 양방향을 고려하여 인접행렬을 작성한다.

인접행렬은 0으로 초기화하여 사용하며 들어오는 값은 경로가 있는 경우이기에, 경로가 없는 경우는 0으로 남는다.

 

- 시작지점의 cost배열

시작 지점에서 갈 수 있는 모든 노드의 cost를 저장할 배열을 설정한다.

 

- check[]배열

시작 지점에서 들린 노드를 check해주기 위해 배열을 생성한다.

 

<예제> 최소비용 구하기

 

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

% 주의할점 %

 cost값을 비교할 때 정점을 들리지 않았을 때의 cost값이 0이라면 무조건 정점을 들렸을 때의 cost를 넣어준다.

시작지점에서의 cost배열을 st[]라고 하자

st[]={0};으로 초기화한 상태에서 갈 수 있는 경로만 cost가 주어져 갈 수 없는 경우일때 0이 계속 들어있는다.

이 상태로 cost값을 비교한다면 갈 수 없는 경로는 비교하면 안 되기에, 정점을 들렸을 때의 cost를 삽입해 갈 수 있는 경로를 만들어준다.

 

---