[자료구조] Dijkstra 알고리즘, 그래프의 최단 경로 찾기

Dijkstra 알고리즘

 

Dijkstra 알고리즘은 가중치 그래프에서, 한 정점에서 다른 정점으로 바로 가는 것보다 다른 정점을 거쳐서 가는 가중치 값이 더 효율적인 경우에 그 경로를 최단경로로 정하는 알고리즘이다.

 

 

식으로 표현하면 위와 같다.

정점 v에서 정점 u까지 가는 최단 경로를 찾는 과정에서, v에서 u로 가는 기존에 알고있던 가중치값보다 어떤 k라는 정점을 거쳐서 가는 가중치가 작은 경우, 그 가중치값이 distance[u], 즉 v에서 u로 가는 최단거리로 업데이트되는 것이다.

 

예시 그래프로 자세히 보자.

 

 

위 그래프에서 시작 정점을 0이라고 해두고 시작하자.

0에서 갈 수 있는 정점은 1, 2, 3이다. 이 세 정점에 대하여 간선의 가중치 값을 기록한다.

그려둔 가중치 값 중 가장 작은 값을 가지는 정점으로 이동한다. 여기서는 정점 1로 이동한다.

{0,1} 의 묶음에서 갈 수 있는 정점에 대하여 판단한다.

 

여기서는 2, 3, 4가 될 것이다. 이 정점들에 대하여 더 작은 가중치값이 있다면 업데이트하여 기록한다.

 

정점 1번으로 이동하여 보면, 4번으로의 거리가 8이다. 하지만 시작 정점에서의 거리를 기록하는 것이므로 5+8 = 13이 적히는 것이다

 

이번에는 정점 2로 이동하여 똑같이 수행한다.

 

 

정점 6까지 모두 돌고 나면 이렇게 표가 그려질 것이다.

 

결론적으로 시작 정점이 0일 때, 0에서 한번에 바로 갈 수 없는 정점들에 대해서 대부분 최단거리를 계산하여 갱신한 것을 확인할 수 있다.

정점 4는 0-1-4가 최단거리고, 정점 5는 0-2-5, 그리고 정점 6은 0-3-6이 최단 거리이다.

이러한 최단거리에서 중간에 거쳐가는 정점을 기록해두지 않으면 어떤 정점을 지나왔는지를 알 수 없다.

 

따라서 우리는 거쳐온 정점도 표시하려 한다.

 

위처럼 말이다.

정점 4는 1을 거쳐서 온 경로가 최단경로이고, 정점 5는 2를, 정점 6은 3을 거쳐서 온 경로가 최단경로라는 뜻이다.

 

 

 

위 Dijkstra 알고리즘을 코드로 구현해 보겠다.

Dijkstra 알고리즘

#include <stdio.h>
#include <limits.h> // For INT_MAX

#define N 6 // 그래프의 노드 개수 (예시)

// 다익스트라 알고리즘 함수
void dijkstra(int weight[N][N], int n, int v) {
    int distance[N], selected[N], path[N];
    int i, j, u, min;

    // 초기화
    for (i = 0; i < n; i++) {
        distance[i] = INT_MAX;  // 모든 거리를 초기화
        path[i] = -1;  // 경로를 초기화 (유효하지 않은 경로 표시)
        selected[i] = 0;  // 선택되지 않음으로 초기화
    }
    distance[v] = 0;  // 시작 노드의 거리는 0
    path[v] = v;  // 시작 노드의 경로는 자기 자신

    // 다익스트라 알고리즘
    for (int step = 0; step < n - 1; step++) {
        min = INT_MAX;
        u = -1;

        // 아직 선택되지 않은 노드 중 최소 거리를 가진 노드 선택
        for (i = 0; i < n; i++) {
            if (!selected[i] && distance[i] < min) {
                min = distance[i];
                u = i;
            }
        }

        // 모든 노드가 선택되었거나, 연결된 노드가 없는 경우 루프 종료
        if (u == -1) break;

        selected[u] = 1; // 선택된 노드 표시

        // 선택된 노드를 통해 인접 노드들의 거리 갱신
        for (j = 0; j < n; j++) {
            if (!selected[j] && weight[u][j] != INT_MAX && distance[u] + weight[u][j] < distance[j]) {
                distance[j] = distance[u] + weight[u][j];
                path[j] = u;
            }
        }
    }

    // 결과 출력
    for (i = 0; i < n; i++) {
        printf("Node %d, Distance: %d, Path: %d\n", i, distance[i], path[i]);
    }
}

int main() {
    int weight[N][N] = {
        {0, 5, 6, 10, INT_MAX, INT_MAX},
        {5, 0, INT_MAX, 7, 8, INT_MAX},
        {6, INT_MAX, 0, 8, INT_MAX, 7},
        {10, 7, 8, 0, 9, 6},
        {INT_MAX, 8, INT_MAX, 9, 0, 12},
        {INT_MAX, INT_MAX, 7, 6, 12, 0}
    };
    int start = 0; 

    dijkstra(weight, N, start);

    return 0;
}

 

실행 결과