다익스트라(최단거리) 알고리즘

Dijkstra

  한 A지점에서 또다른 B지점 까지 가는 최단 거리를 구하는 알고리즘은 여러가지가 있습니다. 다익스트라(몇년전에 돌아가셨죠), 플로이드 등이 있습니다. 다익스트라 알고리즘은 A에서 B까지의 최단거리와 경로를 구하는 알고리즘 입니다. 플로이드 알고리즘은 모든 정점끼리의 최단거리를 구합니다.

  다익스트라(Dijkstra, Edsger  W.  Dijkstra) 알고리즘은 A에서 B까지의 최단거리와 경로를 구합니다. 시간 복잡도는 O(N^2)-오더 N 제곱-입니다. 따라서 정점 100개가 있으면 10000번 이하의 반복으로 구할 수 있습니다.

  원리는 그리디-욕심쟁이- 적으로 돌게 되지만 항상-거리가 음수(-) 이거나 싸이클이 없는 그래프 일 때- 최적해가 나옵니다. 그리고 다익스트라 알고리즘으로는 최대거리는 구할 수 없습니다.

  일단 시작점에서 갈 수 있는 곳을 다 봅니다.-그리고 모든 값은 N개의 테이블에 저장을 합니다-  그중 가장 작은 값을 선택하고 그 값에서 다시 모든 것을 봅니다. 그리고 지금까지 갱신했던 최적해보다 작다면 갱신합니다. 언뜻 보면 최단거리가 안 나올듯 하죠?

  이런 그래프가 있고 정점 A에서 정점 E까지의 경로를 탐색해 본다면...

- 테이블은 [ ]로 표시했습니다.

- 갈 수 있는 노드는 { } 안에 표시 했습니다.

- MAX는 가중치-거리-보다 항상 큰 적당한 수 입니다.

----------

초기화

- 시작점 최소값으로 갱신-출발할때는 거리가 0이다-

- 두번째 테이블은 전 노드를 저장하는 것(경로를 구하기 위함)

     A,     B,     C,    D,     E

[     0,MAX,MAX,MAX,MAX] // "최소비용테이블[현재노드]+거리"가 저장됨

[    -1,     0,     0,     0,     0]

가장 작은 A에서 봄 A{B,C}, A check

[0,6,9,MAX,MAX]

[-1,A,A,0,0]

가장 작은 B에서 봄 B{C} B에서 C로 가는 것이 이전에 찾았던 것보다 크므로 갱신 안함.

[0,6,9,MAX,MAX]

[-1,A,A,0,0]

가장 작은 C에서 봄 C{D,E}

[0,6,9,16 (9+7) ,17 (9+8)]

[-1,A,A,C,C]

가장작은 D에서 봄 D{E} 더 크므로 갱신 안함.

[0,6,9,16,17]

[-1,A,A,C,C]

가장작은 E에서 봄. E는 종료점. -끝-

A에서 E까지의 최단 거리는 17이고 경로는 A-C-E이다.

이해가 되셨나요? 경로를 찾는 법은 재귀호출로 돌리면 되겠죠?-속도면으로 while을 돌려도 무방합니다-

그런데 격자모양의 게임에서 이 방법을 쓰기 어려운 이유는...

  만약 맵의 크기가 100X100이면 노드의 갯수는 10000개가 되겠죠? 다익스트라는 N^2이므로 최악에는 100000000(10^8)번 돌아야 합니다. 보통의 펜티엄 컴퓨터는-릴리즈 모드- 100000000(10^8)의 처리를 1초정도에 합니다. 따라서 캐릭터 한번 움직일때마다 1초의 계산 시간이 필요합니다. 버벅이겠죠? 아니면 트릭비슷하게 계산 시간동안 다른 에니메이션을 보여줄수 도 있겠지만 맵 크기가 커져서 1000X1000정도만 된다면...