그래프 - Dijkstra 알고리즘

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

Dijkstra의 최단 경로 알고리즘

하나의 시작 정점으로부터, 모든 다른 정점까지의 최단 경로를 찾는 알고리즘.

≫임의의 두 정점 간의 거리는 항상 최단거리가 된다.

---

생각의 순서

1. 시작정점 = v
2. 정점 v의 인접정점에 대해서, weight[v][*] 값으로 distance[*] 값 초기화 
3. 집합 S에 포함 안된 정점에 대해서,
   • 최소 distance 정점 u를 찾는다.
   • 정점 u를 집합 S에 추가한다.
   • 정점 u의 인접 정점 && 집합 S에 없는 정점에 대해
     • 기존의 거리보다 정점 u를 거쳐가는게 더 빠르면 distance[z] = distance[u] + weight[u][z]

---

알고리즘

shortest_path(G, v):
	S <- { v }
	for 각 정점w in G:
		distance[w] = weight[v][w]
	while S에 포함안된 정점이 있으면 do
		u <- 최소 distance값을 갖는 정점
		S <- S + { u }
		for z in (정점 u의 인접정점) && (S에 없는 정점) do
			if 기존의 거리보다 정점 u를 거쳐가는게 더 빠르면 
				distance[z] <- distance[u] + weight[u][z]

---

그림으로 이해하기

다음 그래프에 대해 Dijkstra 알고리즘을 시행해 최단경로를 구해보자.

단, INF = 999 = 무한대를 나타낸다.

0. 집합 S와 distance[] 배열 초기화

1. 시작정점 0의 인접정점이면서 S에 없는 정점 1과 5에 대해 거리 변경 

- 정점 1의 거리: INF ==> 0 + 29 = 29

- 정점 5의 거리: INF ==> 0 + 10 = 10

STEP 1

2. 최소 거리를 갖는 5를 S에 추가하고, 5의 인접정점이면서 S에 없는 정점 4의 거리 변경

- 정점 4의 거리: INF ==> 10 + 27 = 37

STEP 2

3. 최소 거리를 갖는 정점 1을 S에 추가하고, 1의 인접정점이면서 S에 없는 정점 2와 6에 대해 거리 변경

- 정점 2의 거리: INF ==> 29 + 16 = 45

- 정점 6의 거리: INF ==> 29 + 15 = 44

STEP 3

4. 최소 거리를 갖는 정점 4를 S에 추가하고, 4의 인접정점이면서 S에 없는 정점 3과 6에 대해 거리 변경

- 정점 3의 거리: INF ==> 37 + 22 = 59

- 정점 6의 거리: 44로 유지 (이유: 44 < 37 + 25)

STEP 4

5. 최소 거리를 갖는 정점 6을 S에 추가하고, 6의 인접정점이면서 S에 없는 정점 3에 대해 거리 변경

- 정점 3의 거리: 59로 유지 (이유: 59 < 44 + 18 = 62)

STEP 5

6. 최소 거리를 갖는 정점 2를 S에 추가하고, 2의 인접정점이면서 S에 없는 정점 3에 대해 거리 변경

- 정점 3의 거리: 59 ==> 45 + 12 = 57 

STEP 6

7. 최소 거리를 갖는 정점 3을 S에 추가하고, 3의 인접정점이면서 S에 없는 정점이 없음.

STEP 7

8. S에 포함안된 정점이 더 이상 없으므로 종료.

---

c언어로 구현

#define def_dijkstra
 
#ifdef def_dijkstra
 
#include <stdio.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
#define INF 999
 
typedef struct GraphType {
    int n;
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
 
int distance[MAX_VERTICES];        // 시작정점으로부터의 최단경로 거리
int found[MAX_VERTICES];        // 방문한 정점은 TRUE로 표시
 
// 최소 거리를 갖는 인덱스 i(= 정점) 찾기
int choose(int distance[], int n, int found[])
{    
    int i, min, minpos;
    min = INF;
    minpos = -1;
    for (i = 0; i < n; i++)
    {    
        if (distance[i] < min && found[i] == FALSE)
        {
            min = distance[i];
            minpos = i;
        }
    }
    return minpos;
}
// 현재 found와 distance 배열 값 보이기
void print_status(GraphType* g)
{
    static int step = 1;
    printf("STEP %d:", step++);
    printf("distance: ");
    for (int i = 0; i < g->n; i++) {
        if (distance[i] == INF)
            printf(" * ");
        else
            printf("%2d ", distance[i]);
    }
    printf("\n");
    printf("          found: ");
    for (int i = 0; i < g->n; i++) {
        printf("%2d ", found[i]);
    }
    printf("\n\n");
}
void dijkstra_path(GraphType* g, int start)
{
    // 시작정점 = v
    // 정점 v의 인접정점에 대해서, weight[v][*] 값으로 distance[*] 값 초기화
    found[start] = TRUE;
    distance[start] = 0;
    for (int i = 0; i < g->n; i++) {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
    }
    int i, u, z;
    for (i = 0; i < g->n; i++) {
        print_status(g);
        u = choose(distance, g->n, found); // 최소 거리를 갖는 정점을 찾고,
        found[u] = TRUE;
        // u의 인접정점의 거리 변경하기
        for (z = 0; z < g->n; z++) {
            if (found[z] == FALSE) {
                if (distance[z] > distance[u] + g->weight[u][z])
                    distance[z] = distance[u] + g->weight[u][z];
            }
        }
    }
    print_status(g);
}
int main() {    
    GraphType g = { 7,
        {{0, 29, INF, INF, INF, 10, INF},
        { 29, 0, 16, INF, INF, INF, 15 },
        {INF, 16, 0, 12, INF, INF, INF},
        {INF, INF, 12, 0, 22, INF, 18},
        {INF, INF, INF, 22, 0, 27, 25},
        {10, INF, INF, INF, 27, 0, INF},
        {INF, 15, INF, 18, 25, INF, 0}}
    };
    dijkstra_path(&g, 0);
    return 0;
}
#endif

결과

---

Kruskal, Prim 알고리즘과의 차이점

알고리즘	원리
Kruskal	전체 간선 중에서 가중치가 작은 순서대로 고르기. 단, 사이클 형성하면 안됨.
Prim	현재 시점의 신장트리 집합의 인접정점 중에서 간선의 가중치가 제일 작은 거 고르기. **트리 밖 정점과의 거리 다시 계산 안함.
Dijkstra	신장트리 집합에 방금 막 추가한 정점(u)의 모든 인접정점(adj_u)에 대해, 원래 경로값과 정점 u를 거쳐갈 때의 가중치값을 비교해서 정점 u를 거쳐가는게 더 빠르면 이 값으로 distance[]값 변경. **트리 밖 정점과의 거리 다시 계산. weight[adj_u] > distance[u] + weight[u][adj_u] ==> distance[adj_u] = distance[u] + weight[u][adj_u]

≫ weight[][] : 기존의 가중치가 저장되어 있는 인접행렬.

≫ distance[]: 시작정점에서 신장트리집합S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열.

≫ S: 시작 정점으로부터의 최단경로가 이미 발견된 정점들의 집합

 

시간복잡도

n개의 정점에 대해 주반복문을 n번, 내부반복문이 n번 반복하므로 O(n^2) 이다.