[이코테/Python] 최단경로

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

 

최단경로 알고리즘은 여러가지가 있지만, 다익스트라(Dijkstra) 알고리즘과, 플로이드 워셜(Floyd-Warshall) 알고리즘 두가지만 기술한다.

 

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

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

다익스트라 알고리즘은 '음의 간선'이 없을 때, 정상적으로 동작한다.

 

다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 과정을 반복하기 때문이다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3, 4를 반복한다.

최단경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며, 리스트를 계속 갱신한다.

 

다음과 같은 그래프에서 노드 1 부터 각 노드로 가는 최단거리를 구하는 과정은 다음과 같다.

 

일단, 1번 노드부터 모든노드까지 걸리는 길이를 INF로 설정하고, 1번노드는 길이를 0으로 설정한다.

1	2	3	4	5	6
0	INF	INF	INF	INF	INF

 

1번 노드에서 갈 수 있는 길은 2번, 3번, 4번 노드이다. 이때 걸리는 길이는 자기자신 + 갈 노드까지의 거리이다.

따라서 1번노드를 기준으로 2번노드까지는 (0+2) 인 2, 3번노드까지는 (0+5) 인 5, 4번노드까지의 길이는 (0+1)인 1이다.

 

구한 값으로 표를 다시 초기화시킨다.

1	2	3	4	5	6
0	2	5	1	INF	INF

 

길이를 구했다면 다음 갈 노드를 선택한다. 이미 간 노드를 제외하고, 거리가 가장 짧은 노드는 4번 노드이다. 따라서 4번노드로 이동한다.

 

4번 노드를 기준으로 갈 수 있는 노드는 3번, 5번 노드이다. 

위와 같은 방식으로 계산을 하면 4번 노드에서 작성할 수 있는 표는 다음과 같다.

1	2	3	4	5	6
0	2	4	1	2	INF

 

이때, 2번 노드와 5번 노드의 거리가 같은데 이럴때는 통상 순번이 빠른 노드부터 방문한다. 따라서 2번 노드로 이동한다.

 

똑같은 규칙으로 2번노드에서 갈 수 있는 노드는 3번이다. (4번은 이미 다녀왔기 때문에.)

따라서 3번 노드까지의 비용인 3을 현재까지의 비용과 더해준다.

이때 3번노드까지의 비용이 (2+3)인 5인데, 이미 3번 노드까지의 비용은 4이기때문에 초기화하게되면 값이 더 커지므로 이럴땐 값을 초기화 하지 않는다. 

1	2	3	4	5	6
0	2	4	1	2	INF

 

이후 5번 노드로 가서 갈수있는 노드는 3번, 6번 노드이다. 표를 초기화하면

1	2	3	4	5	6
0	2	3	1	2	4

 

이때 가장 적은 비용인 3번 노드로 이동한다.

 

마지막으로 3번노드에서 갈 수 있는 노드는 6번노드이다. 따라서 표를 다시 초기화한다.

1	2	3	4	5	6
0	2	3	1	2	4

 

이렇게 하면 1번노드에서 2~6번 노드로 이동할 때 최단거리인 표가 완성된다.

 

다익스트라 알고리즘은 한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는것이다.

시간 복잡도는 (V^2)를 가진다. 이때 V는 노드의 갯수이다.

 

코드로 작성하면 다음과 같다.

import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수, 간선의 개수를 입력받기
n, m = map(int,input().split())
#시작 노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[]for i in range(n+1)]
#방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n+1)
#최단거리 테이블은 무한으로 초기화
distance = [INF] * (n+1)

#모든 간선 정보를 입력받기
for _ in range(m):
    a,b,c = map(int,input().split())
    #a번 노드에서 b번 노드로 가는 비용이 3라는 의미
    graph[a].append(b,c)
    
#방문하지 않은 노드 중에서, 가장 최단거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    #시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    #시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n-1):
        #현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문처리
        now = get_smallest_node()
        visited[now] = True
        #현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost
               
#다익스트라 알고리즘 수행 
dijkstra(start)

#모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    #도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    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

위의 코드는 전체 노드의 개수가 5000개 이하일때 가장 효율적인 코드이다.

 

노드의 갯수가 10000개 이상이라면 개선된 다익스트라 알고리즘을 써야한다.

 

1. 개선된 다익스트라 알고리즘

다익스트라 알고리즘의 시간복잡도는 O(V^2) 였다. 하지만, 개선된 다익스트라 알고리즘의 시간복잡도는 O(ElogV)를 보장하여 해결할 수 있다. V는 노드의 갯수, E는 간선의 갯수이다.

 

다익스트라 알고리즘은 매번 최단거리테이블을 선형적으로 탐색해야했고, 이 과정만 O(V)만큼 시간이 걸렸다. 하지만 선형적으로 찾지 않고, 더 빠르게 찾을 수 있다면 어떨까?

 

개선된 다익스트라 알고리즘은 힙 구조를 사용한다.

힙 자료구조는 간단히 설명해 노드별로 우선순위를 부여해 우선순위가 가장 높은 데이터를 제일 먼저 삭제시키는 알고리즘이다. 트리형태의 알고리즘이다.

스택, 큐, 우선순위 큐를 표로 보면 다음과 같다.

스택	가장 나중에 삽입된 데이터	를 먼저 삭제한다.
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은데이터

힙을 우선순위 큐라고도 한다.

 

더하여, 파이썬에서는 우선순위 큐를 구현할 heapq라는 라이브러리를 제공하고 있다.

우선순위 큐를 구현할 라이브러리로, PriorityQueue 혹은 heapq를 사용할 수 있는데, heapq가 더 빠르게 동작하기 때문에 heapq를 일반적으로 사용한다.

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

#노드의 개수, 간선의 개수를 입력받기
m, n = map(int,input().split())
#시작노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
#최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

#모든 간선의 정보를 입력받기
for _ in range(m):
    a,b,c = map(int,input().split())
    #a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c)) #집합으로 입력받기
    
def dijkstra(start):
    q = []
    #시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0,start))
    distance[start] = 0
    while q: #큐가 비어있지 않다면
        #가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        #현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        #현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            #현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
#다익스트라 알고리즘을 수행
dijkstra(start)

#모든 노드로 가기 위한 최단거리를 출력
for i in range(1, n + 1):
    #도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance == INF:
        print("INFINITY")
    #도달할 수 있는 경우, 거리를 출력
    else:
        print(distance[i])

 

개선된 다익스트라 알고리즘은 우선순위 큐 구조를 사용하고 있기 때문에 get_smallest_node()라는 함수를 작성할 필요가 없다는 특징이 있다.

 

2. 플로이드 워셜 알고리즘

다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단경로 알고리즘이다.

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

 

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 2차원 리스트에 최단거리 정보를 저장한다.

또한, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다.

즉, 점화식에 맞게 2차원 리스트를 갱신하면 된다.

 

점화식은 다음과 같다.

여기서 Dab 는 a에서 b까지 가는 거리를 뜻하고, min함수는 인자들 중에서 가장 작은 값을 반환한다는 함수이다.

 

이 점화식을 이용해 전체적으로 3중 반복문을 이용해 최단거리 테이블을 갱신하면 된다.

 

다음과 같은 그래프가 있다고 할때 2차원 리스트는 다음과 같다.

도착/출발	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

 

이제 1번 노드를 거쳐가는 경우를 생각해보면 된다.

총 여섯가지 경우를 생각하면 되는데 현재 확인하고있는 노드를 제외하고 N-1개의 노드 중에서 서로 다른 노드 (A,B)쌍을 선택하기 때문이다. 

n-1P2개의 쌍을 단계마다 확인하면 된다.

따라서 여섯개의 값을 다시 갱신하면

도착/출발	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

가 된다.

 

이번엔 2번 노드를 거쳐가는 경우 생각을 해보면

(1,3), (1,4), (3,1), (3,4), (4,1), (4,3)으로 여섯가지 경우의 수가 나온다. 이는 1,2,3,4번 노드 중, 2번 노드를 제외하고 1,3,4번 노드에서 2개의 노드를 뽑는 경우의 수이다.

이렇게 뽑은 경우의 수를 위의 점화식으로 계산하면 다음과 같은 리스트가 된다.

도착/출발	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

3번 노드에 동일한 과정을 진행하면

도착/출발	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

마지막으로 4번 노드에 진행하면

도착/출발	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

이렇게 모든 노드에서 모든 노드로 가는 최단경로가 구해졌다.

 

INF = int(1e9)

#노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
#2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1,n+1):
    for b in range(1, n+1):
        if a==b:
            graph[a,b] = 0
            
#각 간선에 대한 정보를 입력받아 그 값으로 초기화
for _ in range(1, n+1):
    #A에서 B로 가는 비용 C라고 설정
    a,b,c = map(int,input().split())
    graph[a][b] = c
    
#점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
    
for a in range(1, n+1):
    for b in range(1, n+1):
        #도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == INF:
            print("INFINITY", end=' ')
        #도달할 수 있는경우, 거리를 출력
        else:
            print(graph[a][b], end=' ')
    print()