자료구조 - 다익스트라 그림으로 쉽게 이해하기

자료구조 - 다익스트라 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 다익스트라 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

정말 그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

 

 

 

- 다익스트라

이번 시간에는 그래프의 최단거리 탐색 알고리즘인 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.
그래프에서 최단 경로를 찾아내기 위한 경로는 많이 있지만 그 중에서 가장 기본이 되는 알고리즘이 다익스트라 알고리즘입니다. 다른 최단경로 알고리즘은 다익스트라를 베이스로한 알고리즘이 많아요. 그래서 다익스트라를 이해하는게 먼저겠죠.

다익스트라는 가중치가 있는 그래프 상의 한 vertex에서 다른 vertex가지의 최단경로를 구하는 알고리즘입니다. 이때 가중치는 음수를 가질수 없고 양수인 경우에만 다익스트라 알고리즘을 적용할 수 있습니다. 이런 제약에도 불구하고 사실 실제 우리가 현실세계에서 그래프로 해결하고자 하는 문제에서 가중치는 대부분 양수 값을 가지기 때문에 충분히 유용하게 쓰이고 있습니다. 가중치에 음수가 있을 경우에는 벨만포드나 플로이드워셜 같은 최단경로 알고리즘을 적용할 수도 있습니다. 이번 포스팅에서는 가장 기본이 되는 다익스트라 알고리즘만 다루겠습니다.

 

 

- 다익스트라 기본 컨셉

우선 다익스트라의 기본 컨셉을 이해하기 위해 아래 그림을 보겠습니다.

 

 

다익스트라 기본 컨셉 이해 그림 예시

 

A에서 G라는 도시로 이동을 해야 한다고 가정을 해보겠습니다.
이때 A에서 G도시 까지 이동하는 그래프는 위 그림과 같이 몇 가지로 나타낼 수 있을겁니다.

 

1) A에서 B도시를 거치고 G도시로 가는 방법

2) A에서 B도시를 거치고 E도시를 거쳐서 G도시로 가는 방법

3) A에서 C도시를 거치고 E도시를 거쳐서 G도시로 가는 방법

4) A에서 C도시를 거치고 F도시를 거쳐서 G도시로 가는 방법

5) A에서 D도시를 거치고 F도시를 거쳐서 G도시로 가는 방법

 

이때 각 도시로 이동하데 걸리는 시간을 아래 그림과 같이 나타낸다고 가정해보겠습니다.

 

각 도시별 이동하는데 걸리는 시간

 

 

먼저 1번 방법인 A에서 B도시를 거치고 G도시로 가는 방법으로 이동했을 때는 4시간 + 7시간으로 총 11시간이 소요되겠죠.  마찬가지로 2번 방법인 A에서 B도시를 거치고 E도시를 거쳐서 G도시로 가는 방법으로 이동했을 때는 4시간 + 2시간 + 1시간으로 총 7시간이 소요됩니다.

 

같은 방법으로 3번 방법으로는 3시간 + 5시간 + 1시간으로 총 9시간이 소요되고, 4번 방법으로는 3시간 + 1시간 + 2시간으로 6시간이 소요되고, 마지막 5번 방법으로는 5시간 + 6시간 + 2시간으로 총 13시간이 소요됩니다. 이렇게 덧셈뺄셈으로 직접 계산해 봤을때는 A에서 G도시 까지의 최단경로는 4번 방법이 가장 빠른 경로가 되겠죠. 그런데 이렇게 최단경로는 찾아가는 방법을 다익스트라 알고리즘은 어떤 식으로 찾아가는지 같이 알아보겠습니다.

 

 

- 다익스트라에서 최단경로를 찾아가는 방법

다익스트라에서는 최단경로는 찾아가는 방법은 "부분경로에서 최단경로의 집합"이라는 명제로 접근을 합니다. 이게 무슨 말인지 그림으로 같이 설명드리겠습니다.

 

다익스트라 구현 예시

 

먼저 A에서 시작을 했을때 갈 수 있는 도시는 B, C, D도시가 있습니다. 그리고 각각 소요되는 시간은 B도시 4시간, C도시 3시간, D도시 5시간입니다. 

 

그 다음 B도시에서 갈 수 있는 도시를 보면 E와, G가 있습니다. E도시로 간다고 했을때 2시간이 소요되므로 총 6시간을 소요하게 되고, G도시로 바로 간다고 했을때는 7시간이 걸리므로 총 11시간이 소요됩니다.

 

 

 

다익스트라 그래프 구현 예시

 

 

이번에는 C도시에서 갈 수 있는 도시를 보겠습니다.

C에서 갈 수 있는 도시는 E와 F가 있습니다. C에서 E를 가기 위해서는 5시간이 걸리므로 E도시 까지 가는데 총 8시간이 소요됩니다. 그런데 8시간이나 걸리는 A에서 C도시를 거쳐 E를 가는 방법보다 6시간이 걸리는 A에서 B도시를 거쳐 E도시를 가는 경로가 더 짧기 때문에 A - E - C 경로는 탈락하게 됩니다. 사용을 안한다는 말입니다. 그래서 다익스트라 그래프 구현 예시입니다.

 

C에서 갈 수 있는 도시가 하나 더 있었죠. 바로 F입니다. F도시 까지는 1시간이 걸리니 A - C - F의 경로로는 총 4시간이 소요되겠네요.

 

 

다익스트라 그래프 구현 예시

 

 

다음으로 D도시에서 갈 수 있는 도시는 F도시 하나뿐입니다. 시간은 D에서 F까지는 6시간이 걸리니 A - D - F 경로의 총 소요시간은 11시간입니다. 그런데 조금 전에 C도시를 경유해서 오면 4시간밖에 안걸렸죠. 그래서 11시간이 걸리는 A - D - F 경로도 사용하지 않고 거르게 됩니다. 그래서 A도시에서 F도시까지 가는 최단 경로는 A - C - F경로입니다.

 

이제 남은 것은 E와 F에서 G도시로 가는 경로인데요. E도시에서 G도시까지는 1시간이 걸리기 때문에 지금까지의 최단경로였던 A - B - E경로의 6시간에 1시간을 더해서 총 7시간이 소요됩니다. 처음에 A에서 B를거쳐 G도시로 바로 가는 경로는 11시간이 소요 됐는데 E를 경유해서 가면 7시간이 걸렸으므로 우리가 알아낸 최단경로로 업데이트를 해주게 됩니다.

 

 

다익스트라 그래프 구현 예시

 

 

마지막으로 F도시에서 G도시를 가게 되다면 2시간이 걸리므로 4시간에서 2시간을 더해 총 6시간이 소요됩니다. 그래서 이전까지 우리가 찾아낸 경로 중 가장빠른 경로였던 E도시를 경유했던 경로보다 빠릅니다. 그래서 G도시로 도착하는 최단 경로를 F도시를 경유하는 경로로 업데이트를 해주게 됩니다. 그래서 최종적으로 A도시에서 G도시까지 갈 수 있는 최단경로로는 A - C - F - G경로이고, 이때 소요시간은 총 6시간이 되는것입니다.

 

 

다익스트라 그래프 구현 예시

 

다익스트라는 전체경로의 최단경로를 찾기 위해서 중간 중간 부분 노드에서의 최단 경로를 찾고, 새로 탐색한 경로가 이전에 찾았던 경로보다 더 짧은 경로라면 해당 경로로 업데이트를 합니다. 그리고 최종적으로 목적지 노드에 도달했을 때에 최단거리를 찾아내는거죠.

 

 

- 정리 및 요약

정리하자면 다익스트라는 시작노드로부터 연결되어 있는 노드들을 탐색하여 탐색하는 시점에 해당 노드까지 가능한 최단경로로 갱신을 합니다. 그리고 최종 목적지 노드에서 최단거리 경로를 최종적으로 업데이트 합니다. 그럼 최종 목적지 노드까지의 최단경로 정보를 어딘가에는 저장해야겠죠? 다익스트라에서는 이 정보들을 기본적으로 배열에 저장을 한다고까지 알고 계시면 되겠습니다.

 

오늘은 이렇게 자료구조 - 다익스트라 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 포스팅도 기대해주세요.

감사합니다.