Dijkstra Algorithm

Dijkstra Algorithm

• 대표적인 최단경로 알고리즘
• 음의 간선 정보가 없는 가중치그래프의 최단 경로 알고리즘이다.

Dijkstra Algorithm 동작 방식

• 개요는 시작점으로부터 정점 v의 최단 거리를 거리 테이블에 갱신하면서 동작한다.

1. 시작점을 설정한다.
2. 시작점으로 부터 최소거리 정보를 거리 테이블에 저장한다. 시작점과 직접 연결된 간선 정보가 없는 정점은 무한대 또는 -1로 저장한다.
3. 현재부터 가장 가까운 거리의 정보를 거리 테이블에 저장한다.
4. 방문처리되지 않은 방금 저장한 정점으로 부터 특정한 노드로 가는 거리 정보를 갱신한다. 방금 위치에 있는 정점을 방문처리 한다.
5. 3,4의 과정을 반복한다.

#include <stdio.h>
int num = 6;
int INF = 10000000;

//전체 그래프를 초기화합니다.
int graph[6][6] = {
    {0,2,5,1,INF,INF},
    {2,0,3,2,INF,INF},
    {5,3,0,3,1,5},
    {1,2,3,0,1,INF},
    {INF,INF,1,1,0,2},
    {INF,INF,5,INF, 2,0}
};


bool visited[6]; //방문한 노드입니다.
int distance[6]; //거리입니다.

//가장 최소 거리를 가지는 정점을 반환합니다.
int getSmallIndex() {
    int min = INF;
    int index = 0;
    for (int i = 0; i < num; ++i) {
        if (distance[i] < min && !visited[i]) {
            min = distance[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start) {
    //start(시작점)으로 부터 현재 알고있는 최소거리 값 초기화
    //graph로 표현된 시작점으로부터의 간선거리 거리값 복사
    //매번 이동하면서 이곳에 갱신된 최소 거리가 기록될 것임
    for (int i = 0; i < num; ++i) {
        distance[i] = graph[start][i];
    }

    //시작노드를 방문처리 해준다.
    visited[start] = true;

    for (int i = 0; i < num - 2; ++i) {
        //방문하지 않은 곳 중 가장 최소 거리를 가지는 정점을 반환합니다.
        int current = getSmallIndex();

        //최소거리 가지는 정점으로 이동, 방문처리
        visited[current] = true;
        //j는 갱신할지 여부를 따질 정점을 의미
        //모든 정점마다 갱신할지 여부를 확인
        for (int j = 0; j < 6; ++j) {
            if (!visited[j]) {
                //시작점으로부터 현재 정점까지의 거리 + 그래프의 저장된 현재정점으로 부터 특정 정점 까지의 거리
                //즉, 시작점부터 현재 정점을 거쳐 특정 정점으로 가는 거리
                int dist = distance[current] + graph[current][j];
                //거쳐서 가는 거리가 더 빠르다면 갱신
                if ( dist < distance[j]) {
                    distance[j] = dist;
                }

            }
        }
    }
}


int main() {
    dijkstra(0);
    for (int i = 0; i < num; ++i) {
        printf("%d ", distance[i]);
    }

    return 0;
}

-------------------------------------------------------------------------------------------------------------

출처 : 다양한 예제로 학습하는 데이터 구조와 알고리즘(나라심하 카루만치 저, 인사이트), 나동빈 유튜브