다익스트라 알고리즘(Dijkstra's Algorithm) 총 정리 - 개념, 원리, 동작 예시, 시간복잡도, 장단점, 주의점, C언어, Java, Python 예시코드

다익스트라 알고리즘 총 정리

 

다익스트라 알고리즘은 최단 경로를 찾는 대표적인 알고리즘으로, 그래프에서 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 계산하는 데 사용됩니다. 이번 글에서는 다익스트라 알고리즘의 개념, 원리, 동작 과정, 시간 복잡도, 장단점, 주의점, 그리고 C, Java, Python 예제 코드를 자세히 다루겠습니다.

 

 

 

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

다익스트라 알고리즘은 가중 그래프(Weight Graph)에서 특정한 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 탐욕적인 접근법(Greedy Algorithm)을 기반으로 하며, 음의 가중치를 가지지 않는 그래프에서만 사용할 수 있습니다.

 

 

2. 다익스트라 알고리즘의 원리

다익스트라 알고리즘은 다음과 같은 원리로 동작합니다.

1. 출발 노드를 설정하고, 출발 노드를 제외한 모든 노드의 최단 거리를 무한(∞)으로 초기화합니다.
2. 현재 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택합니다.
3. 해당 노드를 거쳐 다른 노드로 가는 거리를 계산하여 최단 거리를 갱신합니다.
4. 모든 노드를 방문할 때까지 2~3번 과정을 반복합니다.

 

3. 다익스트라 알고리즘의 동작 예시

예제 그래프

다음과 같은 그래프를 가정해 보겠습니다. A에서 다른 점들까지의 최단 거리를 다익스트라 알고리즘을 활용해서 구해보겠습니다.

        (A)
       /   \
      4     2
     /       \
   (B)---3---(C)
     \       /
      5     1
       \   /
        (D)

 

실행 과정

1. 시작 노드를 A로 설정합니다. 초기 거리 값은 {A: 0, B: ∞, C: ∞, D: ∞}
2. A에서 B(4), C(2)로 가는 거리 갱신 {A: 0, B: 4, C: 2, D: ∞}
3. C가 최단 거리(2)이므로 C에서 D(1)로 이동 {A: 0, B: 4, C: 2, D: 3}
4. D에서 B(5)를 거쳐 가는 거리(3+5=8)는 기존 B(4)보다 크므로 갱신하지 않음
5. B를 방문하여 최단 경로 완성 {A: 0, B: 4, C: 2, D: 3}

 

 

4. 다익스트라 알고리즘의 시간 복잡도

• 인접 행렬(Adjacency Matrix)을 사용하는 경우: O(V^2) (V: 노드 개수)
• 우선순위 큐(힙)를 사용하는 경우: O((V + E) log V) (V: 노드 개수, E: 간선 개수)

 

 

5. 다익스트라 알고리즘의 장단점

장점

• 최단 경로를 빠르게 구할 수 있음 (특히, 힙을 사용하면 시간복잡도 측면에서 대부분의 경우 효율적임)
• 직관적이고 구현이 쉬움

단점

• 음의 가중치를 가진 그래프에서는 사용할 수 없음

 

 

6. 다익스트라 알고리즘의 주의점

• 음수 가중치를 허용하지 않으므로, 벨만-포드 알고리즘과 비교하여 적용할 그래프를 선택해야 합니다.
• 시간 복잡도를 고려하여 적절한 자료구조(배열 vs. 우선순위 큐)를 선택해야 합니다.

 

 

7. 다익스트라 알고리즘 예제 코드

C 언어

#include <stdio.h>
#include <limits.h>
#define V 4

int minDistance(int dist[], int visited[])
{
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (visited[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void dijkstra(int graph[V][V], int src)
{
    int dist[V];
    int visited[V] = {0};
    
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;
    
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = 1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

 

Java

import java.util.*;
class Dijkstra {
    static final int V = 4;
    int minDistance(int dist[], boolean visited[]) {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        return min_index;
    }
    void dijkstra(int graph[][], int src) {
        int dist[] = new int[V];
        boolean visited[] = new boolean[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, visited);
            visited[u] = true;
            for (int v = 0; v < V; v++)
                if (!visited[v] && graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }
    }
}

 

Python

import sys

def dijkstra(graph, start):
    n = len(graph)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    while len(visited) < n:
        min_node = min((node for node in graph if node not in visited), key=lambda node: distances[node])
        visited.add(min_node)
        for neighbor, weight in graph[min_node].items():
            new_distance = distances[min_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
    return distances

 

다익스트라 알고리즘은 최단 경로를 찾는 효율적인 방법으로, 다양한 그래프 문제에서 활용됩니다. 힙을 활용하면 성능을 더 개선할 수 있으며, 이에 대해서는 다음 글에서 다룰 예정입니다.