35. Dijkstra 알고리즘

다익스트라 알고리즘이란?

다익스트라 알고리즘은 시작 노드로부터 다른 모든 노드까지의 최단거리를 찾는 알고리즘이다.

이 알고리즘은 그리디 알고리즘의 일종으로,

현재까지 발견된 최단거리가 가장 작은 노드를 선택하여 최단거리를 갱신하는 방식으로 동작한다.

---

다익스트라 알고리즘 구현

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 1000 // 최대 노드 개수
#define INF INT_MAX // 무한대

int graph[MAX_VERTICES][MAX_VERTICES]; // 그래프
int dist[MAX_VERTICES]; // 최단거리
int visited[MAX_VERTICES]; // 방문 여부

int dijkstra(int start, int n) {
    // 초기화
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[start] = 0;

    for (int i = 0; i < n - 1; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
                u = j;
        }

        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != 0) {
                int alt = dist[u] + graph[u][v];
                if (alt < dist[v]) {
                    dist[v] = alt;
                }
            }
        }
    }
}

int main() {
    // 그래프 초기화
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
    }

    // 그래프 생성
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;
    }

    // 다익스트라 알고리즘 실행
    int start;
    scanf("%d", &start);
    dijkstra(start, n);
    
    // 결과 출력
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        }
        else {
            printf("%d ", dist[i]);
        }
    }

    return 0;
}

 

Dijkstra() 함수의 역할

1. 초기화 : 시작 노드로 부터 각 노드까지의 거리를 무한대로 설정한다. (시작 노드의 거리는 0)

2. 방문하지 않은 노드 중에서 현재까지 발견된 최단거리가 가장 작은 노드를 선택한다.

3. 선택된 노드를 방문한 것으로 표시한다.

4. 선택된 노드와 연결된 노드들의 최단거리를 갱신한다.

5. 모든 노드를 방문할 때까지 2~4를 반복한다.

 

이 알고리즘의 시간 복잡도는 O(N^2)이다.

그러나 우선순위 큐를 이용하여 구현하면 시간복잡도를 O(N log N)까지 줄일 수 있다.