반응형

다익스트라 알고리즘의 코드 구현은 다음 사이트의 내용을 참조하였다.


http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/


그리고 다익스트라 알고리즘이 진행되는 과정은 다음 게시물에 수록되어 있다.


http://www.crocus.co.kr/532 :: 다익스트라 개념









<< 다익스트라 알고리즘(Dijkstra Algorithm) 소스 코드 >> 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <limits.h> // INT_MAX에 이용
 
// 정점의 개수를 정의
#define V 5
 
 
int minDistance(int dist[V], bool sptSet[V])
{
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
    {
        if (!sptSet[v] && min > dist[v])
        {
            min_index = v;
            min = dist[v];
        }
    }
 
    return min_index;
}
 
 
// 시작점에서 그 정점까지의 최단 거리를 출력해준다.
void printSolution(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}
 
void dijkstra(int graph[V][V], int src)
{
    int dist[V]; // 최단 거리를 파악하는 배열
    bool sptSet[V]; // 방문 했는지 체크 하는 bool형 배열
 
    for (int i = 0; i<V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
 
    // 초기 조건 설정.
    dist[src] = 0;
 
    // V-1번 루프를 수행한다는 것은 첫 src노드를 제외한 모든 노드들에 접근을 해 계산을 한다는 의미.
    for (int count = 0; count < V - 1; count++)
    {
        // 최단거리 정보를 알고 있는 노드들 중 가장 거리가 짧은 노드의 인덱스를 가져온다.
        int u = minDistance(dist, sptSet);
 
        // 그래프 상의 모든 노드들을 탐색하며 u 노드의 주변 정보를 갱신한다.
        for (int v = 0; v < V; v++)
        {
            // 1. 아직 처리가 되지 않은 노드이어야 하며 (무한루프 방지)
            // 2. u-v 간에 edge가 존재하고
            // 3. src부터 u까지의 경로가 존재하고
            // 4. 기존의 v노드까지의 최단거리 값보다 새로 계산되는 최단거리가 더 짧을 경우
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[v] > dist[u] + graph[u][v])
            {
                // 최단거리를 갱신해준다.
                dist[v] = dist[u] + graph[u][v];
            }
        }
 
        // 이제 이 노드(u)는 접근할 일이 없다. 플래그를 true로 설정.
        sptSet[u] = true;
 
        // 현재까지의 최단 거리를 출력해준다.
        printSolution(dist, V);
    }
}
 
int main()
{
    // 다익스트라를 이용할 그래프
    int graph[V][V] = 
    { 
        { 0368},
        { 3024},
        { 6205},
        { 8450},
        { 7852},
    };
 
    // dijkstra(최단 거리를 구하고자 하는 그래프, 시작 하고자 하는 정점);
    dijkstra(graph, 0);
 
    return 0;
}
 
Crocus






결과 값은 다음과 같고, 이 과정에 대한 내용은 http://www.crocus.co.kr/532 에 자세히 수록되어 있다.


반응형