자다가도 일어나서 바로 구현할 수 있어야하는 최단경로를 찾는 다익스트라 알고리즘 파헤치기 1편

1. 최단경로

 

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소인 경로

 

최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.

 

다양한 종류가 있지만 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다

 

예를 들어 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우",

 

"모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"

 

최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다.

 

 

2. 다익스트라 최단경로 알고리즘

 

그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

 

시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식

 

시작정점(s)에서 끝정점(t)까지의 최단 경로에 정점 x가 존재하여, 최단경로는 "s에서 x까지의 최단 경로"와 "x에서 t까지의 최단 경로"로 구성

 

"음의 가중치"를 가지는 간선이 없어야 한다.

 

실제 세계에서도 음의 가중치를 가지는 간선은 존재할 수 없으니, 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택될 정도로 중요하다.

 

기본적으로 그리디 알고리즘으로 분류된다.

 

매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

 

 

2-1) 알고리즘 원리

 

1) 출발 노드를 설정한다

 

2) 최단 거리 테이블을 초기화한다

 

3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다

 

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다

 

5) 위 과정 3),4)를 반복한다

 

다익스트라 알고리즘은 최단 경로를 구하는 과정에서

 

"각 노드에 대한 현재까지의 최단 거리"정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다

 

매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다

 

나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 "더 짧은 경로도 있었네?"하면서

 

이제부터는 이 경로가 더 짧은 경로야라고 판단한다.

 

방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인해 반복한다는 의미에서 그리디 알고리즘으로 볼 수 있다

 

 

3. 예시를 통해 이해하는 다익스트라 알고리즘

 

다음과 같은 그래프에서 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제를 생각해보자.

 

출발 노드는 1이라고 설정한다.

 

초기 상태에서는 다른 모든 노드로 가는 최단 거리를 "무한"으로 초기화한다.

 

코드로는 999999999,987654321 등과 같이 매우 큰 수를 사용할 수 있다.

 

혹은 지수표기법으로 1e9같이 10억을 나타낼 수 있는데 파이썬에서는 실수로 나타나므로 정수형이 필요하다면 int(1e9)라고 하면 된다

 

먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데,

 

출발 노드에서 출발 노드의 거리는 0으로 보기때문에 처음에는 출발 노드를 선택

 

 

이제 출발노드인 1번노드에서, 최소 비용으로 선택된 1번 노드를 거쳐 다른 노드로 가는 비용을 계산

 

1번 노드와 연결된 모든 간선을 하나씩 확인한다

 

위 그림에서 1번에서 2,3,4로 가는 비용은 1번에서 1번으로 가는 비용은 0이므로 각각 0+2 = 2, 0+5= 5, 0+1=1

 

현재 2,3,4번으로 가는 비용은 "무한"으로 설정되어 있는데, 현재 더 짧은 경로를 찾게 되었다.

 

각각 새로운 값으로 갱신한다

 

 

 

이제 갱신된 테이블 D를 보고 아직 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야한다. 

 

따라서 이번엔 4번 노드가 선택된다.

 

 

다음 이제 1번에서 4번까지는 왔고, 4번을 거쳐서 갈 수 있는 경로들을 확인하면 된다

 

갈 수 있는 노드는 3번과 5번이다.

 

각각 최단 비용은 1-4까지 비용이 1이고 4-3까지 비용은 3이므로 1-4-3으로 가는 비용은 1+3 = 4이고

 

1-4까지 비용이 1이고 4-5까지 비용이 1이므로 1-4-5로 가는 비용은 1+1 = 2이다.

 

이제 3번까지 가는 비용이 원래 5가 있는데 더 작은 4로 가는 경로를 찾았고

 

5번까지 가는 비용은 무한이었는데 더 작은 2로 가는 경로를 찾았으므로 테이블을 갱신

 

 

다시 테이블에서 거리가 가장 짧은 노드를 선택한다.

 

현재 방문하지 않은 노드인 2,3,5,6중에서 거리가 가장 짧은 노드는 2,5로 2개이다.

 

이런 경우 번호가 작은 노드를 선택하는 것이 일반적이다.

 

그래서 2번 노드를 선택한다

 

 

이제 선택된 2번 노드를 거쳐서 도달할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지를 확인하자.

 

1-2로 가는 최소 비용은 현재 2이다. 

 

여기에 2번에서 갈 수 있는 곳은 3번과 4번인데, 1-2-3으로 가는 비용은 2+3 = 5이고 1-2-4로 가는 비용은 2+2=4이다.

 

모든 경우에 3번까지 가는 최소 비용은 4이고 4번까지 가는 최소 비용은 1이므로 갱신되지 않는다.

 

 

다음으로 방문하지 않은 노드인 3,5,6중에서 거리가 최소인 5번 노드를 선택한다.

 

그리고 5번을 거쳐서 갈 수 있는 경로들을 모두 확인한다

 

 

현재 1번 노드에서 5번 노드까지의 최단 거리는 2이다. 여기에 5번에서 3번,6번으로 가는 비용은 각각 1,2이다.

 

그러므로 1-4-5-3까지 가는 최단 비용은 2+1 = 3이고 1-4-5-6으로 가는 최단 비용은 2+2=4이다.

 

현재 3번까지 최단 비용이 4이고 6번까지 최단 비용은 무한이므로 더 짧은 경로를 찾았다.

 

그러므로 테이블을 갱신한다

 

 

다음으로 방문하지 않은 노드 중에서 최소 거리를 가지는 노드는 3번 노드이다.

 

3번 노드에서 갈 수 있는 노드는 2번과 6번이다.

 

1번에서 3번까지 가는 최소 비용이 3이므로, 1----3-2까지 가는 비용은 3+3 = 6이고, 1-----3-6까지 가는 비용은 3+5=8이다.

 

하지만 현재 테이블의 최소 비용은 각각 2,4이므로 갱신되지 않는다.

 

 

마지막으로 방문하지 않은 노드 중에서 남은 6번 노드를 선택하고 갈 수 있는 노드 중에서 비용을 계산하여 최단 거리이면 갱신한다.

 

하지만 6번에서 갈 수 있는 노드는 없으니 갱신하지 않고 종료

 

 

이렇게 나온 최종 최단 거리 테이블이 의미하는 바가 뭘까?? 지금까지 잘 따라왔다면..

 

1번 노드에서 출발하여 1,2,3,4,5,6번 노드로 갈때 최단 거리로 가는 비용이 각각 0,2,3,1,2,4라는 의미가 된다.

 

위에서 볼 수 있듯이 다익스트라 최단 경로 알고리즘은

 

"방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드"를 선택하는 과정을 반복한다

 

이렇게 매 단계마다 선택된 노드는 "최단 거리"가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다

 

위 과정을 보면 모든 과정에서 실제로 한 번 선택된 노드는 최단 거리가 감소하지 않는다.

 

즉 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이다.

 

그러므로 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.

 

즉 위에서 6번 노드를 선택할 때 이미 나머지 5개의 노드의 최단 거리는 확정된 상태이므로 더 이상 갱신될 수가 없다.

 

 

4. 다익스트라 알고리즘 기본형 구현 예시

 

다익스트라 알고리즘의 기본형은 노드의 개수 V에 대하여 $O(V^{2})$이고 다익스트라에 의해 처음 고안된 알고리즘이다.

 

처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언

 

단계마다 "방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택"하기 위해 매 단계마다 1차원 리스트의 모든 원소를 순차 탐색한다.

 

 

##다익스트라 알고리즘(인접리스트 표현)

def dijkstra(start):
    
    ##시작 노드에 대해 거리는 0으로 초기화
    distance[start] = 0

    ##시작 노드 방문 처리
    visited[start] = 1

    for b,w in graph[start]: ##시작 정점과 인접한 b와 가중치 w에 대하여
        
        distance[b] = w ##시작 정점에서 b로 가는 최단 거리는 모두 w
    

    ##시작 노드를 제외한 전체 v-1개의 노드에 대해 반복하기

    for _ in range(v-1):
        
        ##distance 배열을 순차탐색하여 
        ##방문하지 않은 노드 중에 최단 거리가 짧은 노드 번호를 찾는다
        
        u = 0
        min_w = INF

        for i in range(1,v+1): ##정점의 번호가 1번부터 v번까지 일때...
            
            if visited[i] == 0 and distance[i] < min_w: ##아직 방문하지 않았고, 거리가 현재 최솟값보다 작을때,
                
                u = i
                min_w = distance[i]
        
        ##반복문을 돌면..최단거리를 가지는 노드 u를 찾았다

        visited[u] = 1

        for b,w in graph[u]: ##u와 연결된 노드 b를 확인한다
            
            ##b까지 가는 최단 비용은..
            ##원래 최단 비용과 (u까지 가는 최단비용+ u에서 b로 가는 가중치w) 사이 최솟값
            distance[b] = min(distance[b], distance[u]+w)


##노드의 개수, 간선의 개수를 입력받는다

v,e = map(int,input().split())

## 시작 노드 번호

start = int(input())

##인접리스트로 노드의 연결 정보

graph = [[] for _ in range(v+1)]

##방문한 적이 있는 노드인지 체크

visited = [0]*(v+1)

##최초 최단 거리 테이블을 무한으로 초기화

INF = int(1e9)

distance = [INF]*(v+1)

##모든 간선 정보를 입력받는다

for _ in range(e):
    
    a,b,w = map(int,input().split())

    ##a번에서 b번으로 가는 비용이 w

    graph[a].append((b,w))


##다익스트라 알고리즘 수행

dijkstra(start)

##각 노드 1번부터 v번까지 가는 최단 비용 출력

for i in range(1,v+1):
    
    if distance[i] == INF: ##무한이면.. 갱신이 안된것으로 도달할 수 없다는 의미
        
        print('infinity')
    
    else: ##도달 가능
        
        print(distance[i])
"""
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
0
2
3
1
2
4
"""

 

 

 

자세히 보니까 프림 알고리즘 기본형이랑 완전히 똑같네???

 

distance가 key배열이고.. visited가 MST배열이랑 똑같아

 

위 코드는 노드의 개수가 너무 많아서 메모리상으로 인접행렬을 사용할 수 없을 때 사용가능하다.

 

인접행렬을 사용할 수 있을 때는 다음과 같이 사용할 수 있을 것이다

 

주의할 점은 매번 선택한 노드와 인접한 노드를 확인해야하는데

 

그러한 조건이 "if adjM[start][i] > 0 and adjM[start][i] < INF:"

 

최단거리 테이블 갱신할때는 노드가 방문하든 말든 상관없이, 선택한 노드와 연결된 노드를 확인해야함

 

최단거리 테이블 최초 초기화할때도, 0이 아니라 무한이 들어가야하거든..

 

그래서 인접행렬을 

 

adjM = [[INF]*(v+1) for _ in range(v+1)]로 생성하거나

 

최초 초기화할때, start와 인접한 노드의 거리를 넣을 수 있도록..

 

for i in range(1,v+1):
        
 if adjM[start][i] > 0 and adjM[start][i] < INF: ##i가 start와 인접해있다면..
        
 distance[i] = adjM[start][i]"""

 

##다익스트라 알고리즘(인접행렬 표현가능)

def dijkstra(start):
    
    ##시작 노드에 대해 초기화

    distance[start] = 0 ##시작노드 거리는 0

    visited[start] = 1 ##시작 노드 방문 체크

    ##시작 노드에서 다른 노드 i까지 가는 최소 거리는...
    ##인접한 노드까지 거리 그대로

    for i in range(1,v+1):
        
        if adjM[start][i] > 0 and adjM[start][i] < INF: ##i가 start와 인접해있다면..
        
            distance[i] = adjM[start][i]
    
    ##시작 노드를 제외한 전체 v-1개의 노드에 대해 반복

    for _ in range(v-1):
        
        ##현재 distance 배열을 순회하여
        ##최단 거리가 가장 짧은 노드를 선택하여 방문 처리

        u = 0
        min_w = INF

        for i in range(1,v+1): ##정점의 번호가 1번부터 v번까지 일때,
            
            ##아직 방문하지 않았고, 최단거리 distance[i]가 가장 짧은 i를 찾는다
            if visited[i] == 0 and distance[i] < min_w: 
                
                u = i
                min_w = distance[i]
        
        ##반복문을 모두 돌면 최단거리를 가진 노드 u를 찾았다

        visited[u] = 1

        for i in range(1,v+1): ##정점의 번호가 1번부터 v번까지 일때,
            
            if adjM[u][i] > 0 and adjM[u][i] < INF: #u와 인접한 i에 대하여..
                
                #i번 노드의 최단거리는..
                ##현재 최단거리 vs. 선택된 노드 u+u에서 i까지 가는 가중치 중 최솟값으로 갱신
                distance[i] = min(distance[i], distance[u]+adjM[u][i])

##노드의 개수, 간선의 개수를 입력받는다

v,e = map(int,input().split())

##시작 노드 번호를 입력받는다

start = int(input())

##인접행렬 생성
##1번부터 v번까지

adjM = [[0]*(v+1) for _ in range(v+1)]

##방문한 적이 있는지 체크하는 배열

visited = [0]*(v+1)

##최단 거리 테이블을 최초 무한으로 초기화

INF = int(1e9)
distance = [INF]*(v+1)

##모든 간선 정보를 입력받는다

for _ in range(e):
    
    a,b,w = map(int,input().split()) ##a번 노드에서 b번 노드로 가는 가중치가 w

    adjM[a][b] = w ##방향그래프니까 여기까지

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

##출발노드에서 1번부터 v번까지 최단거리 출력
for i in range(1,v+1):
    
    if distance[i] == INF: ##최단거리가 무한이면, 갱신되지 않았으므로 도달 불가능
        
        print('infinity')
    
    else: ##최단거리가 무한이 아니면 도달 가능
        
        print(distance[i])

"""
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
0
2
3
1
2
4
"""

 

 

5. 시간복잡도

 

시간 복잡도는 $O(V^{2})$이다. 총 O(V)번에 걸쳐서 최단 거리가 짧은 노드를 매번 선형 탐색해야하며

 

현재 노드와 연결된 노드를 매번 일일이 확인하기 때문이다.

 

전체 노드의 개수가 5000개 이하라면 이 코드가 통하겠지만, 10000개 이상이면 너무 느려져서 이 코드를 사용하기 어렵다.