다익스트라(Dijkstra) 알고리즘 최단경로 알고리즘

📍 다익스타라 알고리즘 이란? 

다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점(node)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 모든 정점까지의 최단거리를 각각 구하는 알고리즘으로, 최단 경로 문제에 사용된다. 

그래프 방향의 유무는 상관이 없지만, 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 

 

다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 이 과정에서 도착 정점(node) 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 그래서 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 

 

다익스트라는 매 단계마다 현재까지 가장 가까운 정점을 선택해서 그 정점에서 갈 수 있는 거리를 업데이트 한다. 또한 배열에 각 정점까지의 최단 거리를 계속 저장하고, 이전에 계산된 거리보다 더 짧은 경로가 생기면 업데이트 하는 방식 이다. 때문에 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다. 

 

 

 

💡 다익스트라 알고리즘 동작원리 

다익스트라 알고리즘은 기본적으로 두 단계를 반복한다. 

1. 해당 노드로부터 갈 수 있는 노드들의 비용( 거리값 )을 갱신한다. (다이나믹 프로그래밍)

2. 방문하지 않은 노드 중에서 가장 비용( 거리값 )이 적은 노드를 선택한다. (그리디 알고리즘)

 

cf) 임의의 노드에서 다른 노드로 가는 값을 비용이라고 한다. 

 

 

예를 들어,

아래와 같은 그래프가 있다고 해보자.

집에서 출발해 학교까지 도착하는 최단 경로를 구하려고 한다. 

 

출발지부터 각 노드까지의 최단 거리를 기록할 표를 distance라고 하겠다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	∞	∞	∞	∞	∞	∞

 

출발지에서 출발지까지의 거리는 당연히 0이라는 값을 가진다. 

출발지인 집을 제외한 나머지 노드들은 거리를 알 수 없기 때문에 거리값은 " ∞ "이 된다. 

 

이제 출발지인 집을 시작으로 Loop를 돌며 아래의 두 단계를 반복할 것이다. 

1. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다
2. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

 

---

1️⃣  현재 노드 : 집

집에서 갈 수 있는 이웃 노드들은 '미용실', '슈퍼마켓', '영어학원'이다. 

각 노드의 거리값은 '미용실' : 5 , '슈퍼마켓' : 10, '영어학원' : 9이다. 

 

1). 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신.

distance에는 출발지부터 각 노드들로 가는 최단거리를 기록한다. 

현재 distance에 집에서 미용실로 가는 최단거리는  ∞ 이다.

이 기존값과 비교하여 지금 계산한 거리값이 최소값이면 distance를 업데이트 해준다. 

 

가령 미용실의 경우  ∞ 와 5중 작은 값인 5를 택해 업데이트 해준다. 

다음과 같이 인접한 노드까지의 거리를 모두 업데이트 한다. 

그리고 방문한 '집'노드는 방문 표시를 한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	10	9	∞	∞	∞

 

 

2). 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택.

이제 집에서 갈 수 있는 노드들은 거리값을 다 확인했다. 

그럼 다음으로는 어디를 가야할까? 

 

👉  방문하지 않는 노드 중  가장 거리값이 작은 곳을 다음 노드로 선택한다. 

 

그럼 다음 방문 장소는 미용실이 된다.

 

 

---

2️⃣ 현재노드 : 미용실

 

이제 미용실 노드에서 위의 과정을 반복한다. 

미용실 노드에서 갈 수 있는 노드는 '슈퍼마켓', '은행'이다. 

각 노드의 거리값은 '슈퍼마켓' : 3 , '은행' : 11이다. 

 

우리가 구하려는 거리값은

"출발지부터 해당 노드까지의 거리값"이기 때문에 다음과 같이 계산할 수 있다.

👉 "출발지부터 현재 노드까지의 거리 + 현재 노드 부터 가려고 하는 이웃노드의 거리" 

 

 

1). 출발지 부터 현재 노드까지의 거리값은 distance['미용실']로 5이고 

여기에 미용실 부터 이웃노드 까지의 거리값을 더해주면 된다. 

계산하면 다음과 같다. 

• 집에서 부터 슈퍼마켓 까지의 거리는 5 + 3 = 8,
• 집에서 부터 은행 까지의 거리는 5 + 11 = 16 이다. 

2). 이제 지금 계산한 값을 바탕으로 distance를 업데이트 해준다. 

슈퍼마켓 부터 살펴보자. 

• distance에 저장된 슈퍼마켓까지의 거리값은 10이다. 
• 방금 계산한 슈퍼마켓까지의 거리는 8이다. 
• 10 > 8 이므로 값을 업데이트 한다. 

다음은 은행이다.

• distance에 저장된 은행까지의 거리는 ∞이다. 
• 방금 계산한 은행까지의 거리는 16이다. 
• ∞ > 16이므로 값을 업데이트 한다. 

3). 그리고 방문한 노드를 표시한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	∞	16	∞

 

4). 다음 방문할 노드는 슈퍼마켓이다. 

방문하지 않은 노드중에서 거리값이 가장 작기 때문이다. 

 

---

3️⃣ 현재 노드 : 슈퍼마켓

 

슈퍼마켓 노드에서 갈 수 있는 노드는 '레스토랑', '영어학원', '은행'이다. 

각 노드의 거리값은 '레스토랑' : 3, '영어학원' : 7, '은행' : 10 이다. 

 

1). 출발지 부터 현재 노드까지의 거리값은 distance['슈퍼마켓']으로 8이고 

여기에 슈퍼마켓부터 이웃노드 까지의 거리값을 더해주면 된다. 

계산하면 다음과 같다. 

• 집에서 부터 레스토랑 까지의 거리는 8 + 3 = 11,
• 집에서 부터 영어학원 까지의 거리는 8 + 7 = 15,
• 집에서 부터 은행 까지의 거리는 8 + 10 = 18 이다. 

2). 지금 계산한 값을 바탕으로 distance를 업데이트 해준다. 

레스토랑 부터 살펴보자. 

• distance에 저장된 슈퍼마켓까지의 거리값은  ∞ 이다. 
• 방금 계산한 레스토랑까지의 거리는 11이다. 
•  ∞  > 11 이므로 값을 업데이트 한다. 

다음은 영어학원이다.

• distance에 저장된 영어학원까지의 거리는 9이다. 
• 방금 계산한 영어학원까지의 거리는 15이다. 
• 9 < 15이므로 업데이트 하지 않는다. 

다음은 은행이다.

• distance에 저장된 은행까지의 거리는 16이다. 
• 방금 계산한 은행까지의 거리는 18이다. 
• 16 < 18이므로 업데이트 하지 않는다. 

3). 그리고 방문한 노드를 표시한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	11	16	∞

 

 

4). 다음 방문할 장소는 영어학원이다. 

방문하지 않은 노드중에서 거리값이 가장 작기 때문이다. 

---

4️⃣ 현재 노드 : 영어학원

영어학원 노드에서 갈 수 있는 노드는 '은행', '학교'이다. 

각 노드의 거리값은 '은행' : 7, '학교' : 12 이다. 

 

1). 출발지 부터 현재 노드까지의 거리값은 distance['영어학원']으로 9이고 

여기에 영어학원부터 이웃노드 까지의 거리값을 더해주면 된다. 

계산하면 다음과 같다. 

• 집에서 부터 은행 까지의 거리는 9 + 7 = 16,
• 집에서 부터 학교 까지의 거리는 9 + 12 = 21,

2). 지금 계산한 값을 바탕으로 distance를 업데이트 해준다. 

은행부터 살펴보자. 

• distance에 저장된 은행까지의 거리값은  16 이다. 
• 방금 계산한 은행까지의 거리는 16이다. 
•  16 = 16 이므로 업데이트하지 않는다. 

다음은 학교이다.

• distance에 저장된 학교까지의 거리는 ∞ 이다. 
• 방금 계산한 학교까지의 거리는 21이다. 
• ∞ > 21이므로 값을 업데이트 한다.

3). 그리고 방문한 노드를 표시한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	11	16	21

 

 

4). 다음 방문할 장소는 레스토랑이다. 

방문하지 않은 노드중에서 거리값이 가장 작기 때문이다. 

---

5️⃣ 현재 노드 : 레스토랑

레스토랑 노드에서 갈 수 있는 노드는 '은행' 이다. 

각 노드의 거리값은 '은행' : 4 이다. 

 

1). 출발지 부터 현재 노드까지의 거리값은 distance['레스토랑']으로 11이고 

여기에 레스토랑부터 이웃노드 까지의 거리값을 더해주면 된다. 

계산하면 다음과 같다. 

• 집에서 부터 은행 까지의 거리는 11 + 4 = 15,

2). 지금 계산한 값을 바탕으로 distance를 업데이트 해준다. 

은행을 살펴보자. 

• distance에 저장된 은행까지의 거리값은  16 이다. 
• 방금 계산한 은행까지의 거리는 15이다. 
•  16 > 15 이므로 값을 업데이트 한다.

3). 그리고 방문한 노드를 표시한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	11	15	21

 

 

4). 다음 방문할 장소는 은행이다. 

방문하지 않은 노드중에서 거리값이 가장 작기 때문이다. 

 

---

6️⃣ 현재 노드 : 은행

은행 노드에서 갈 수 있는 노드는 '학교' 이다. 

각 노드의 거리값은 '학교' : 2 이다. 

 

1). 출발지 부터 현재 노드까지의 거리값은 distance['은행']으로 15이고 

여기에 은행부터 이웃노드 까지의 거리값을 더해주면 된다. 

계산하면 다음과 같다. 

• 집에서 부터 학교 까지의 거리는 15 + 2 = 17,

2). 지금 계산한 값을 바탕으로 distance를 업데이트 해준다. 

학교를 살펴보자. 

• distance에 저장된 학교까지의 거리값은  21 이다. 
• 방금 계산한 은행까지의 거리는 17이다. 
•  21 > 17 이므로 값을 업데이트 한다.

3). 그리고 방문한 노드를 표시한다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	11	15	17

 

 

4). 도착지를 제외한 모든 노드를 방문했다 - 종료!!

 

---

✔ 이렇게 최종 distance를 보면 다음과 같다. 

집	미용실	슈퍼마켓	영어학원	레스토랑	은행	학교
0	5	8	9	11	15	17

 

최종 distance를 통해 출발지부터 각 노드까지의 최단 거리를 구할 수 있었다. 

 

---

💡 다익스트라 알고리즘 구현

다익스트라 알고리즘은 '방문하지 않은 노드'를 다루는 방식에서 순차 탐색을 할것인지 우선순위 큐를 쓸것인지로 나뉜다.  

 

1️⃣ 순차 탐색

다익스트라 알고리즘은 방문하지 않은 노드 중 거리값이 가장 작은 노드를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이다. 

 

순차탐색은 거리 테이블의 앞에서부터 찾아낸다. 그래서 노드의 개수만큼 순차 탐색을 수행해야 한다.
따라서 노드 개수가 N개 라고 할 때, 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 (N−1)×N 👉 O(N^2)의 시간이 걸린다.

 

구현을 할 때 위에서 설명했 듯 distance를 저장할 배열 하나와 방문여부를 나타내는 배열을 사용한다.

import sys

input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())
start = int(input())

# 주어지는 그래프 정보 담는 리스트 
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) # 방문여부 기록
distance = [INF] * (n+1) # 거리값 기록

for _ in range(m) :
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

# 다음에 방문할 노드 반환
# -> 방문하지 않은 노드 이면서 시작노드와 최단거리인 노드 
def get_smallest_node():
    min_value = INF
    index = 0 
    for i in range(1, n+1) :
        if not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i 
    return i 

# 다익스트라 알고리즘 
def dijkstra(start) :
    #시작노드 -> 시작노드 거리 계산 및 방문처리 
    distance[start] = 0 
    visited[start] = True

     # 시작 노드의 인접한 노드들에 대해 최단거리 계산
    for i in graph[start]: 
        distance[i[0]] = i[1]

    # 시작노드 제외한 n-1개의 다른 노드들 처리
    for _ in range(n-1) : 
        now = get_smallest_node() # 다음 방문할 노드 반환
        visited[now] = True # 해당 노드 방문 처리
        # 해당 노드의 인접한 노드들 간의 거리 계산 
        for next in graph[now] : 
            cost = distance[now] + next[1]
            if cost < distance[next[0]] :
                distance[next[0]] = cost

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF : 
        print('도달할 수 없음')
    else : 
        print(distance[i])

코드 출처 : https://techblog-history-younghunjo1.tistory.com/247

# 입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

 

 

2️⃣ 우선순위 큐 

우선순위 큐를 이용하는 다익스트라 알고리즘의 핵심 아이디어는 '항상 현재까지의 최단 경로를 가진 노드를 빠르게 선택하는 것'이다.

이 과정을 좀 더 자세히 설명하면 다음과 같다. 

 

다익스트라 알고리즘은 아직 방문하지 않은 노드 중에서 현재까지 계산된 최단거리가 가장 작은 노드를 선택해야 한다.

이를 위해 모든 노드를 매번 확인하는 대신, 우선 순위 큐를  사용하면 최소 비용 노드를 O(logN)시간에 찾을 수 있다. 

이 연산은 최대 N번 (노드 수만큼) 발생하므로, 총 O(NlogN)의 시간이 소요된다. 

 

현재 선택한 노드에서 인접한 노드들의 거리를 갱신할 때, 만약 인접한 노드로 가는 경로의 비용이 기존에 저장된 비용보다 작으면, 그 값을 갱신하고 우선 순위 큐에 새롭게 삽입한다. 

이 과정은 모든 간선(E)에 대해 발생할 수 있다.

👉 우선순위 큐에 삽입하는 연산까지 고려하면 총 O((N+E)logN)의 시간 복잡도를 가지게 된다. 

 

만약 인접 노드를 갱신할 때마다 무작정 우선순위 큐에 넣는다면, 같은 노드가 여러 번 큐에 들어갈 수 있다. 

이 경우, 실제로 한 노드를 여러번 처리하게 되어 시간 복잡도가 보장되지 않을 수 있다. 

따라서 

• 이미 방문했는지 여부
• 현재 큐에 들어있는 비용과 비교

이 두가지 조건을 통해 불필요한 중복 삽입이나 방문을 방지한다. 

 

 👉 다익스트라 알고리즘에서 우선순위 큐를 잘 활용하면 최소 비용 노드 선택과 인접 노드 거리 갱신을 효율적으로 처리할 수 있고, 전체 시간 복잡도는 O((V+E)logV)가 된다. 

import sys
import heapq


input = sys.stdin.readline
INF = int(1e9)

#노드의 개수, 간선의 개수 입력
n,m = map(int, input().split())
start = int(input())

#그래프 초기화(1번부터 n번까지)
graph = [[] for _ in range(n+1)]
# 시작 노드로부터 각 노드까지의 최단 거리 초기화 
distance = [INF] * (n+1)

# 간선 정보 입력 
for _ in range(m) : 
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

def dijkstra(start) : 
    # 우선순위 큐 초기화 : (거리, 노드번호)
    q = [] 
    heapq.heappush(q, (0, start))
    distance[start] = 0 #시작 노드까지의 거리는 0

    while q : 
        # 가장 최단 거리가 짧은 노드 추출
        dist, now = heapq.heappop(q)
        # 이미 더 짧은 경로가 있다면 무시 
        if distance[now] < dist : 
            continue
        # 현재 노드와 연결된 인접 노드 확인
        for next_node, weight in graph[now] : 
            cost = dist + weight
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))

# 다익스트라 알고리즘 실행 
dijkstra(start)

# 각 노드까지의 최단 경로 출력
for i in range(1, n+1):
    if distance[i] == INF:
        print("도달할 수 없음")
    else:
        print(distance[i])

 

C++로 구현한 코드 

#include <cstdio>
#include <vector>
#include <climits>
#include <queue>
using namespace std;

#define INF INT_MAX


// 1) 그래프 만들기
typedef struct{
    int node; // 연결된 다음 노드 번호
    int weight; // 간선의 가중치
}Data;

struct cmp{ //사용자 정의 비교 함수
    bool operator()(Data a, Data b){
        return a.weight > b.weight ; // 가중치 오름차순
    }
};

// queue생성 및 시작노드 정보 삽입/갱신
priority_queue<Data, vector<Data>, cmp> pq;

void InitQueue(int start){
    pq.push({start, 0}) ; //시작하는 노드 삽입
    Dijk[start] = 0; // Dijk[시작] = 0으로 갱신
}

vector <Data> v[6];

void MakeGraph(){
    // 1번 노드와 연결된 그래프 생성
    v[1].push_back({2, 8});
    v[1].push_back({3, 2});
    // 2번 노드와 연결된 그래프 생성
    v[2].push_back({1, 8});
    v[2].push_back({4, 10});
    // 3번 노드와 연결된 그래프 생성
    v[3].push_back({1, 2});
    v[3].push_back({4, 1});
    v[3].push_back({5, 7});
    // 4번 노드와 연결된 그래프 생성
    v[4].push_back({2, 10});
    v[4].push_back({5, 9});
    // 5번 노드와 연결된 그래프 생성
    v[5].push_back({3, 7});
    v[5].push_back({4, 9});
}

// 2) 최단 경로 값을 담을 배열 생성 및 초기화 
int Dijk[6]; // Dijk[x] : x번 노드까지의 최단 경로 값

void InitDijkArray(){
    for(int i = 1; i<= 5; i++){
        Dijk[i] = INF;
    }
}

// Dijkstra 구현
void DijkStra(){
    while(!pq.empty()){
        //priority_queue 맨앞노드 가져오기
        Data nowNode = pq.top();
        pq.pop();

        int node = nowNode.node;
        int weightSum = nowNode.weight;

        if(Dijk[node] < weightSum) continue; // 이미 이전에 더 적은 가중치로 Dijk[node]를 갱신함
        // nowNode와 연결되어 있는 다른 모든 노드 탐색
        for(int i = 0; i< v[node].size(); i++){
            int nextNode = v[node][i].node;
            int weight = v[node][i].weight;

            // 다음 노드에 저장된 값 > 다음 노드로 방문하면서 소비할 가중치의 합   --> 일때만 값 갱신, 그리고 pq삽입
            if(Dijk[nextNode] > weight + weightSum) {
                Dijk[nextNode] = weight + weightSum;
                pq.push({nextNode, Dijk[nextNode]});
            }
        }
    }
}

int main(void){
    MakeGraph();
    InitDijkArray();
    InitQueue(1); //노드 1을 시작이라고 가정

    DijkStra();
}

코드 출처 : https://meojiktard.tistory.com/13

 

C++로 구현하면 다음과 같다. 

이렇게 코드 작성하시는 분들은 진짜 객체 지향을 잘 활용하시는것 같다. 

보면서 정말 많이 배운다. 

아직도 주먹구구 진행방향으로 나열하듯이 일자로 코드를 짜는 나... 

반성해..  :-)

 

 

---

참조 

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

https://cobi-98.tistory.com/46

[필수 알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 이해

https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 다익스트라(Dijkstra) 알고리즘

https://meojiktard.tistory.com/13

[알고리즘] 다익스트라 - 최단 경로 구하기(Dijkstra), C/C++