1. 개요

 이번 글에서는 드디어 내게 수많은 시련과 아픔을 줬던 알고리즘인 다익스트라 알고리즘을 작성한다. 다익스트라 알고리즘

은 방향성이 있고 가중치가 있는 그래프에서 노드에서 노드까지 최단 거리를 찾는 알고리즘이다. 이 알고리즘은 취업 관문

에서 2번이나 만나본 알고리즘이다. 최고의 게임 회사 중 하나에서 최종 코딩테스트에서 나온 문제이기도 하고 최고의 

소셜커머스 기업에서 코딩 문제로 나온 문제이기도 하다. 그리고 나는 나올 때 마다 풀긴 풀었는데 뭔가 미흡하게 풀었고

결과는 탈락이었다. 왜냐하면 그 당시의 나는 STL을 쓰지 않고 미련하게 모든 자료구조 하나하나 다 내가 만들어서 풀려고

했기 때문에 언제나 시간이 부족했다. 다익스트라 알고리즘의 특성상 우선순위 큐 만들기도 힘든데 그 제한 시간동안 우선

순위 큐인 힙을 만드는데 주어진 시간 대부분을 써버리고 정작 알고리즘에 넣어서 최종 테스트할 시간하기도 벅찼기 때문

이다. 그래서 이번 기회에 확실하게 정리해서 다시는 틀릴 일 없도록 머릿속에 담아둔다.

 다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm)을 사용한다. 탐욕 알고리즘이란 현재 상황에서 여러가지 경우가

있을 경우 그 순간의 최선의 선택을 하는 알고리즘이다. 그 순간 순간 최선을 선택해 결국 최종적으로 답을 도출하지만 

이렇게 얻은 문제의 답이 전체적으로 최선이라고 보장되지는 않는다.


 필요한 재료는 다음과 같다.

 (1) 시작 노드에서 각 노드들의 최단 거리를 기록하는 거리 배열(일차원 배열)

 (2) 시작 노드에서 끝 노드까지 경유한 노드를 기록하는 경로 배열(일차원 배열)

     ( 구조: Path[CurrentNodeIndex] = BeforeNodeIndex, 각 노드 인덱스의 배열값은 이전 노드 인덱스이다. )  

 (3) 우선순위 큐 (왜 일반 큐가 아닌 우선순위 큐일까?, 왜 음의 가중치는 안될까? (답은 해설에서))

 

 알고리즘은 다음과 같다.

 (1) 거리 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 아직 계산 안한 노드 의미)

 (2) 경로 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 이전 노드가 없다는 의미)

 (3) 현재 노드에서 연결된 노드들을 우선순위 큐에 넣는다. 우선순위 큐이므로 최단거리로 정렬된다.

     (시작점 일 경우, 시작 노드를 큐에 넣는다.)

 (4) 현재 노드와 연결된 노드들 사이의 최단거리를 찾아서 거리 배열과 경로 배열을 채운다.

 (5) (3) ~ (4)을 모든 노드를 방문할 때 까지 반복한다.


2. 문제

 다음 그림에서 다익스트라 알고리즘을 작성하시오. (STL 사용시 편함)



3. 코드

3-1) 메인

3-2) 다익스트라(Dijkstra Alg) 알고리즘


3-3) 경로추적 알고리즘


3-4) 출력


4. 해설

 드디어 다익스트라 알고리즘 정리가 끝났다. STL을 안썼을때는 코드가 그렇게 커졌는데 STL을 쓰기 시작하니

코드가 기하급수적으로 줄어든다. 참 편리하다. 지금 생각하면 아쉽다. 진작 STL 썼으면 최종 코딩 테스트에서

무난히 통과했을 것 같았는데, 괜히 무리하게 모든건 다 만들어서 하려고 했던 내가 미련스럽다. 하지만 그런

과정이 있었으니 지금 더욱 발전했겠지.


 다음은 해설이다.

 (1) 왜 우선순위 큐를 쓸까?

 결론적으로 말해서 최소거리 값 갱신 횟수의 증가때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과

에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다. 다익스트라 알고리즘에서 

속도에 영향을 주는 요소는 큐에서 노드를 꺼내오는 횟수우선순위 큐의 갱신 횟수이다. 이게 무슨 뜻이냐면 

예를들어 보자. 만약 위의 예제에서 일반 큐를 쓴다면 A에서 검사를 시작할 때, 연결된 두 노드 B와 C중 B부터 

검사한다. 하지만 우선순위 큐라면 C부터 검사한다. 왜냐하면 우선순위 큐로 인해 최소 거리로 정렬된 순서로 

큐에서 추출되기 때문이다. 이 상황을 정리하면


A에서 E까지 최소거리를 검사할 때

일반 큐)

A -> B -> C -> E -> B -> D -> E -> E 순으로 검사

첫 번째 E 노드를 검사할 때, 현재 B까지 최소거리는 4, C까지 최소거리는 1, E까지 최소거리는 8이 된다.

하지만 그 다음 B노드를 검사할 때 B의 최소거리가 3으로 갱신되기 때문에 이전에 계산한 작업이 

무의미한 값이 된다. 이런 경우가 일반 큐를 사용할 때 나타나는 시간상의 비효율적인 대표 예이다.


우선순위 큐)

A -> C -> B -> B -> D -> E -> E -> E 순으로 검사

이 검사는 이전에 계산해둔 값이 그 단계에서 최소값이라는 것이 보장되기 때문에 갱신 횟수가 현저히 적어진다.


 이해를 돕기위한 작은 예지만 그래프의 크기가 커지면 커질수록 이런 일반 큐와 우선순위 큐 사이의 중복갱신

횟수가 일반큐가 월등히 많아지게 된다. 그러므로 최종적으로 일반 큐에서는 O(E+V^2)에서 우선순위 큐 사용 시

O(ElogV)으로 시간상의 이점이 발생하게 된다. (V는 정점 수, E는 엣지 수)


 (2) 왜 음의 가중치는 계산을 못할까? 

결론적으로 말해서 그 이유는 이전 노드까지 계산해둔 최소거리 값이 최소라고 보장할 수 없기 때문이다.

다익스트라는 정점을 지날수록 가중치가 증가한다 라는 사실을 전제하고 쓰여진 알고리즘이다. 하지만 음의

가중치가 있다면 정점을 지날수록 가중치가 감소할 수도 있다는 의미가 되므로 앞선 전제가 무너진다. 그러므로

다익스트라 알고리즘에서는 음의 가중치를 계산할 수 없다. 하지만 이와같은 점을 음의 가중치에서도 최소거리를

계산하는 벨만-포드 알고리즘이 존재한다.  


*현재 이 코드는 정점 이름을 숫자로 표기하면 상관없지만 고유 이름으로 나타낼 수 없다. (지명 이름을 표기하고 싶으면 추가 작업 필요)



  1. 커피한잔 2016.06.09 01:04

    좋은 정보 잘보고 갑니다

  2. 질문 2016.08.04 21:19

    질문이 있는데 우선순위 큐에 이미 들어간 것 중에서 값이 갱신되버리는 경우는 어떻게 하나요? 포인터로 집어넣은게 아니라 값으로 집어넣은 것이라서 그 경우는 고려되지 않는게 아닌가요?

    • 안녕하세요. 제가 잘 이해했는지 모르겠지만, 우선순위 큐에 이미 들어간 것 중에서 값이 갱신되는 경우는 어차피 각 노드의 방문은 딱 1번씩만 이뤄집니다. 즉, 이 노드에서 연결된 노드를 다시 큐에 넣었다가 이 노드가 중복된 노드라면 그냥 빠져나오고 맙니다. 그리고 값으로 집어넣은게 아니라 값을 기준으로 우선순위큐에 정렬시킨 노드를 넣은 경우입니다. 즉 노드 구조체에 대한 포인터를 고려합니다.

  3. asdf1234 2016.08.19 05:05

    좋은 글 감사합니다.

    공부하는데 많은 도움이 되었습니다.

    궁금한 점이 한가지 있는데 만약 무방향 그래프라면 어떻게 해야할 지 잘 몰르겠습니다.

    예를 들면 from : 1, to : 2, weight : 3 from : 2, to : 1, weight : 3 이런식으로 두번 넣어줘야 할까요??

    • 안녕하세요.
      만약 무방향 그래프라는 가정으로
      질문 주셨는데 몇 일 동안 생각해본 결과

      일단 최단거리 알고리즘이기에
      왔던 길을 다시 돌아가는 행위는 일어날 수 없습니다.

      그러므로 똑같이 방문 노드를 기준으로 최단 거리를 측정해야 하는데

      방향 그래프든 무방향 그래프든 다익스트라 알고리즘은 모든 경우를 고려해서 최단거리를 측정합니다.

      그렇기에 써주신대로 2가지 방향이 있다면 두 방향의 엣지를 큐에 넣어주고
      큐에서 dequeue했을 때 나온 to 값이 이미 방문한 노드라면 더이상 검사안하게 작성하면 될 것 같습니다.

      결론은 현재 알고리즘에서 방향이든 무방향이든 그 엣지를 큐에 넣으면 됩니다.

  4. 챠밍 2016.10.04 23:41

    struct Graph* newAdjMatrixofGraph() 이건 무슨 뜻인가요?

    • 안녕하세요. 챠밍님. 그건 다익스트라 알고리즘과 상관없이 입력 데이터를 위해 2차원 그래프 데이터를 생성하는 함수입니다. 저 함수가 실행되면 위 문제의 인풋 그래프 값이 자동으로 생성되게 만들었습니다.

  5. algorist 2017.07.17 00:37

    잘보았습니다~ 특히 우선순위 큐부분 잘보았습니다

  6. DarknessX7 2018.04.30 22:33

    정말 감사드립니다.
    덕분에 C++을 활용하는데 필요한 지식을 쌓고 갑니다.

  7. PEACE- 2018.06.05 15:16 신고

    안녕하세요!! 잘읽었고 숙지하는데 큰 도움이 됐습니다.
    다만 경로추적 알고리즘 구현 부분에서 파라미터로 받은 start를 받을 필요없이 해결되는 알고리즘을 짜주셨기 때문에
    파라미터를 굳이 받을 필요가 없다고 말씀드릴려구 댓글 달았습니당...핳

    • 안녕하세요. 먼저 말씀해주셔서 감사합니다. 아무래도 지금 다시보니 조금 미숙한 부분들이 많지만 ㅠㅠ언제 시간나면 말씀해주신 부분들 반영해서 재포스팅 하도록 해보겠습니다~! 감사합니다~!

  8. 2018.06.20 20:49

    비밀댓글입니다

    • 안녕하세요~! 먼저 글 좋게 읽어주셔서 감사합니다~! 내용은 언제든지 쓰셔도돼요 블로그 번창하시길 바라고 언제나 행복가득하셔요~!

  9. 코돈 2018.08.03 19:13

    네트워크 이론에 관심 있는 고등학생입니다
    가중치 있는 그래프의 최단 경로가 궁금해서 다익스트라 알고리즘에 대해 계속 찾아보고 있는데 계속 이해를 못하겠네요..ㅠ

    구하는 과정은 어찌어찌 이해가 가는데 최단 경로를(시작점에서 어디를 거쳐 마지막에 도착하는지) 어떻게 구하는지 모르겠습니다..

    이 글의 그림만 봐도 A C B E 가 최단 경로인것 같은데 그 결과가 어떻게 유도되는지 모르겠습니다. 제가 이해를 잘 하고 있는지도 모르겠네요..

    • 안녕하세요. 음 ... 저도 다익스트라가 처음에는 정말 이해가 안갔는데 명확히 설명하기가 참 어려워서 답글 달기까지 오래걸렸네요. 말씀주신 부분인 '시작점에서 어디를 거쳐 마지막에 도착하는지' 에 대한 부분에 대한 답은 결론적으로는 모든 노드를 다 방문해서 거리를 계산하고 그 중에서 최단 거리를 뽑아내는 것입니다. 현재 노드를 기준으로 연결된 노드들을 다음 방문 노드로 설정하여 우선순위 큐에 넣고 현재 노드에 대한 최단거리 계산이 끝나면 큐에서 노드를 꺼내서 이 노드까지의 최단거리를 계산하여 갱신합니다. 이와 같은 동작을 반복하여 더이상 방문하지 않은 노드(즉 최단거리를 계산하지 않은 노드)가 없으면 알고리즘이 종료됩니다. 감사합니다.

  10. 쉬다가 2018.11.06 03:02

    newAdjMatrixOfGraph() 의 구현내용을 알 수 없을까요.. 참고해서 해결해보려고 했지만 아직 구조체에 대해 완전하게 알지를 못해서 난감하네요.. 디버깅을 통해 공부를 하고싶은데 알 수 없나요?

    • 안녕하세요! 먼저 좋게 읽어주셔서 감사합니다. 그런데 말씀드린 부분에 대한 코드가 이제 없어서 제가 드릴 수가 없네요. 또 위에 썼듯이 단순히 2차원 구조체에 위 문제에 대한 데이터 입력 부분함수여서 구조체에 대해 조금만 찾아보시면 바로 알 수 있을 것 같습니다. 그래프 데이터를 넣으면서 전 더 이해가 깊어졌던것 같아요. 화이팅입니다~!

  11. 시우 2019.07.15 19:30

    덕분에 도움 많이 받았습니다. 앞 부분 개념 설명 스크랩 해가도 될까요? ^^;

+ Recent posts