다익스트라 알고리즘 ( Djikstra Algorithm )

1. 개요

[그림 1] 가중치배열 ( Weight Array )

다익스트라 알고리즘 ( Dijstra Algorithm ) 은 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾을 때 사용하는 알고리즘이다. 이 알고리즘에서는 어떤 시작점 S가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾을 수 있기 때문에 결과적으로 어떤 최종 목적지 T로 가는 최단 경로를 구할 수 있다.

다익스트라 알고리즘에서 가장 중요하고 핵심이 되는 "가중치 배열 (Weight Array)"은 시작점 S를 기준으로 각 정점의 최단거리를 가리키는 배열이다. 

---

2. 다익스트라 알고리즘 (Dijstra Algorithm) 코드 구현 및 설명

/*-------------------------------------------------------------------------------------- 함수명 및 기능: dijstra() - 전달된 그래프내에 선택된 정점으로 부터 나머지 정점까지의 최소 가중치를 계산하고 부모자식 관계를 연산함 전달인자: g - 그래프 정보 구조체의 주소 vNum - 선택된 정점 번호 weightArray - 가중치를 저장할 배열의 시작주소 parent - 정점간의 부모자식관계를 저장할 배열의 시작주소 리턴값: 없음 --------------------------------------------------------------------------------------*/ void dijkstra(GraphMatrix *g, int vNum, int *weightArray, int *parent) { int i; /*iterator */ int minIndex; /* 체크되지 않은 정점 중 가장 작은 가중치를 저장하고 있는 정점의 인덱스 저장 */ int target; /* 가중치 계산시 대상이 되는 정점의 인덱스 저장 */ int check[MAX_VERTEX]; /* 검사된 정점은 1로 미검사 정점은 0으로 저장 */ int dist; /* 우회 가중치 저장 변수*/ int tmpWeight; /* minIndex를 찾기 위한 가중치 저장 임시 변수 */ /* 기준 정점 vNum 기준으로 weightArray, parent, check 배열 초기화 */ for(i=0; i<g->vertexCnt; ++i) { weightArray[i] = g->graph[vNum][i]; /* 기준 정점 vNum으로 부터 각 정점에 이르는 가중치 저장 */ parent[i] = vNum; /* 부모 노드 정보를 모두 기준 정점으로 해둔다 */ check[i] = 0; /* 체크 여부를 모두 0(체크안됨)으로 초기화 */ } parent[vNum] = -1; /* 기준 정점의 부모는 없으므로 -1(존재할 수 없는 인덱스번호)로 초기화 */ check[vNum] = 1; /* 시작 정점을 vNum 체크 */ printWeightArray(weightArray, vNum, g->vertexCnt); /* 시작 정점 기준으로 가중치 배열 출력 */ /* 가중치가 가장 작은 정점을 기준으로 가중치 배열을 갱신하며 부모 자식 관계를 생성 하는 반복문 */ for(int j=0; j< g->vertexCnt-1; ++j) /* 모든 정점에 대해서 가중치을 갱신하기 위해 반복 */ { minIndex = 0; /* 가중치가 가장 작은 정점을 0이라고 가정 */ tmpWeight = WEIGHT_MAX+1; for(i=0; i<g->vertexCnt; ++i) { if(check[i]==0 && weightArray[i] < tmpWeight) /* 체크되지 않은 정점 중 가장 작은 정점의 인덱스를 찾음*/ { minIndex = i; tmpWeight = weightArray[minIndex]; } } check[minIndex] = 1; /* 찾아낸 가장 작은 가중치 정점을 체크 함 */ for(target=0; target<g->vertexCnt; ++target) /* 타겟 정점이 포함된 가중치로 갱신 */ { /* target이 체크되었거나 (minIndex, target) 간선이 존재하지 않는다면 다음 target검사로 넘어감 */ // if(minIndex==target || check[target] || g->graph[minIndex][target] == WEIGHT_MAX) continue; //<== 생략해도 되나 함께 실행하면 처리속도가 발라짐 dist =weightArray[minIndex] + g->graph[minIndex][target]; /* 우회 경로의 가중치 계산 */ if(dist < weightArray[target]) /* 우회 경로의 가중치가 직접경로의 가중치 보다 작으면 갱신 */ { weightArray[target] = dist; /* 우회 경로 가중치로 갱신 */ parent[target] = minIndex; /* target의 부모노드로 minIndex노드 저장 */ } } printWeightArray(weightArray, minIndex, g->vertexCnt); /* minINdex 기준으로 갱신된 가중치 배열 출력 */ } }

우선 메인함수에서 가중치배열과 부모정점저장 배열을 선언하고 이것들을 다익스트라 함수 전달인자로 넘겨준다.

변수로는 1) minIndex , 2) target , 3) check배열 , 4) dist , 5) tmpWeight 다섯가지가 있다. 1번 변수 "minIndex"의 역할은 정점들 중 가장 작은 가중치를 저장하는 정점의 인덱스를 저장할 변수이다. 2번 변수 "target"은 가중치 계산시 대상이 되는 정점의 인덱스를 저장한다. 그리고 3번 변수 체크배열은 정점이 검사한곳인지 안 한곳인지 판별해주는 아주 중요한 배열이다. 4번 "dist"변수는 우회가중치를 저장하는 변수이고 마지막 5번 tmpWeight는 minIndex를 찾기위해 비교되는 임시 변수이다.

예시로 기준 정점을 "A"라고 하자. A번방 인덱스를 기준으로 전달인자로 받은 가중치배열에 기준 정점으로부터 각 정점의 가중치를 넣어주고, 부모정점배열의 모든 방을 기준정점의 인덱스로 초기화, 마지막으로 체크배열도 모두 0으로 (방문X)로 초기화시켜준다.

이제 기준 정점 "A"를 기준으로 가중치배열을 하나씩 계산하자.

Check배열에 기준정점을 체크시키고 큰 For문 하나를 모든 정점에 대해 반복하도록 설정해준다. 일단 minIndex를 0으로 초기화시키고 tmpWeight도 초기화 해준다.

다음 과정은 가장 가중치가 작은 인덱스를 찾는 과정이다. 이중 for문을 통해 정점갯수만큼 반복시키게 두고 조건을 체크되지 않은 정점 중 가장 작은 정점의 인덱스를  찾는 조건으로 설정한다.

[그림 1]의 경우 가장 작은 정점의 인덱스는 "B"가 될 것이고 "B"를 체크배열에 방문처리해준다.

다음은 가중치배열을 타겟정점이 포함된 가중치로 계산하는 작업을 한다. 정점 "A"부터 시작하여 끝 정점까지 업데이트 해줄것이다. 

[그림 1]의 경우로 A,B정점은 체크되었으니 건너뛰고 C정점도 간선연결이 되어있지않으므로 건너뛴다. (코드에서는 이 판별조건이 주석처리되었다. C도 계산을 할 테지만 가중치가 무한대라 갱신이 되지않을것) 

B정점을 기준으로 한 인접정점들끼리의 가중치를 계산한다. 그림에서는 E정점과 F정점이 있는데 E정점을 계산하면 " dist = 2 ( 시작점 "A"에서 현재 minIndex 정점 "B" 가중치 ) + 5 ( "B"에서 "E" 의 가중치 ) => 7 " 이다.

이 dist값이 직접경로 가중치 weightArray[E] 보다 작으면 갱신 한다. 당연히 시작점 "A"에서 "E" 가중치는 무한대이므로 우회로가 더 빠르다 따라서 갱신한다. dist값으로 갱신하고 부모정점배열도 바꿔준다.

이 과정을 정점 갯수만큼 반복하면 가중치배열이 그때그때 바뀔것이고 마지막에 갱신되는 배열이 최종 최단거리를 나타내게 된다.

---

3. 시작정점기준 각 정점으로의 최단거리 출력

/*-------------------------------------------------------------------------------------- 함수명 및 기능: pathPrint() - 시작 정점->끝 정점까지의 path 및 가중치 출력 전달인자: parent - 부모, 자식관계를 저장한 배열의 시작주소 weightArray - 가중치 저장 배열의 시작주소 startVNum - 시작 정점 번호 endVNum - 도착 정점 번호 리턴값: 없음 --------------------------------------------------------------------------------------*/ void pathPrint(int *parent, int * weightArray, int startVNum, int endVNum) { int i,j=0; int vNum; /* 경로로 선택된 정점 번호 */ char path[MAX_VERTEX]; path[j] = endVNum; vNum = endVNum; /* 도착지 정점 번호부터 검사 */ while(vNum!=startVNum) { vNum = path[++j] = parent[vNum]; } for(i=j; i>=0; --i) /* path 배열을 뒤집어 출력해야 startVNum -> endVNum의 경로가 출력 됨 */ printf("%3c -> ", 'A'+path[i]); printf("\b\b\b (weight: %d)\n", weightArray[endVNum]); }

시작정점을 기준으로 하여 각 정점으로의 최단거리를 출력해주는 함수이다.

가중치배열을 만들때 같이 만들었던 부모정점배열을 이용한다. 

---

4. main()

int main() { GraphMatrix g; int weightArray[MAX_VERTEX]; /* 가중치를 순차적으로 저장하는 배열 */ int parent[MAX_VERTEX]; /* 부모 정점 저장 배열*/ int i; initGraph(&g, "d:\\data\\graphData2.txt");/* 그래프 초기화 */ displayTitle("[가중 그래프의 인접 행렬 출력]"); outputGraph(&g); /* 그래프 연결 및 가중치 상태 출력*/ NEWL; NEWL; /* 다익스트라 알고리즘 수행 */ displayTitle("[가중치 변화 상태 출력]"); dijkstra(&g, 5, weightArray, parent); /* 5번에 해당하는 정점을 기준으로 다익스트라 알고리즘 실행 */ displayTitle("[정점간의 부모, 자식관계 출력]"); printParent(parent, g.vertexCnt); /* parent 배열 출력 */ /* 기준 정점(F-5번 정점)로 부터 그래프태의 모든 정점(A~K)가지의 경로 및 가중치 출력 */ displayTitle("[F(5번 정점)기준으로 각 정점으로의 path 출력하기]"); for(i=0; i<g.vertexCnt; ++i) pathPrint(parent, weightArray, 5, i); return 0; }