최단경로(다익스트라,플로이드워셜)

최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다.

예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다.

 

대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다.

이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다.

 

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

 

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

다시 말해 다익스트라 알고리즘의 구현은 간단한 버전(순차탐색), 성능이 개선된 버전(힙큐 사용) 으로 나뉜다.

간단한 버전의 시간복잡도는 O(v^2)이다.

개선된 버전의 시간복잡도는 O(ElogV)이다. 

일반적으로 간단한 버전의 경우 입력수가 v<5000일경우 사용이 가능하다. 그 이상일 경우에는 개선된 버전을 사용하여야 한다.

플로이드 워셜은 V,E<500일 경우 사용이 가능하다.

V는 노드의수,E는 간선의 수이다.

힙큐대신 우선순위큐를 사용하여도 되지만 힙큐가 성능이 더욱 우수하다.

전체적인 순위가 아닌 맨앞순위가 필요하기 때문에 부모자식간의 서열이 매겨지는 힙큐를 사용하여도 된다.(힙큐는 형제사이에는 순위가 안매겨짐)

https://yunzae.tistory.com/95

힙큐

 

 

1.간단한 버전(순차 탐색)

① 출발 노드와 도착 노드를 설정한다.
② '최단 거리 테이블'을 초기화한다.
③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
⑤ ③~④의 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

 

출발 노드는 1번, 도착 노드는 6번이라 하고 거리 테이블을 전부 큰 값, 여기서는 inf(무한대)로 초기화했다. 각 노드들을 잇는 간선의 가중치 역시 표시했다.

출발 노드를 먼저 선택하고 거리를 0으로 한다.

1번 노드와 연결된 인접 노드는 2, 4이다. 그곳까지 가는 거리를 각각 기존의 거리값과 비교해 최솟값으로 업데이트한다. 가령 2의 경우 inf와 2 중 작은 값인 2를 택해 할당한다.
또한 인접 노드까지의 거리를 모두 업데이트한 1번 노드는 방문 표시를 한다.
최근 갱신한 테이블 기준, 방문하지 않는 노드 중 가장 거리값이 작은 번호를 다음 노드로 택한다. 위 상태에서는 4번 노드이다.

4번 노드에서 같은 작업을 수행한다. 4번과 연결된 2, 5번까지 오는 거리를 계산한다. 가령 5의 경우엔 4번까지 오는 데 필요한 거리 + 4->5 간선의 가중치 값인 2와 기존의 값인 inf 중 최솟값을 계산하고, 2번 노드의 경우엔 기존 값인 2와 4번을 거쳐가는 값인 1+2 = 3을 비교한다. 그렇다면 2번 노드는 기존 값이 더 크므로 업데이트하지 않는다. 즉, 1번에서 바로 2번으로 가는 것이 1->4를 거쳐 2번으로 가는 길보다 더 적게 걸린단 뜻이다.
다음으로 선택될 노드는 아직 방문하지 않은 노드 2, 3, 5, 6 중 거리값이 가장 작은 노드이므로 2 또는 5이다. 거리 값이 같다면 일단 인덱스가 작은 노드를 택한다고 하고 2번으로 가보자.

2번 노드와 연결된 3, 4번 노드에 대해 같은 과정을 반복한다.
그 다음 노드는 3, 5, 6번 중 가장 거리값이 작은 5번 노드가 되겠다.

5번 노드와 연결된 6번 노드에 같은 과정을 반복한다.
다음 노드를 선택해야 하는데, 아직 방문하지 않은 3번과 6번 중 거리값이 작은 것은 6번이다. 그런데 6번은 더 이어지는 노드도 없는데다 도착 노드이다. 따라서 알고리즘을 종료한다.

최종적으로는 1번에서 6번까지 오는 데 1 - 4 - 5 - 6의 경로를 거치고 최소 거리는 4가 된다.

특징

위 동작 예시에서 볼 수 있듯이, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.
도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.

다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다는 중요한 특징이 있다.

위 그림의 상황에서 1 → 4의 경로가 최단경로이려면 3+k가 1보다 커야 한다. 즉, k > -2가 성립해야 한다. 반대로 k가 -5라고 한다면 오히려 1 → 2 → 4 경로가 더 최단 경로가 된다. 그 말인 즉, 1번에서 연결된 노드 중 4번이 가중치가 적다는 이유로 최단 거리를 1이라 할 수는 없다는 이야기이다.
따라서 다익스트라 알고리즘을 사용하기 위해서는 정점 사이를 잇는 간선의 가중치가 양수여야 한다. 그래야 한 번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 되는 것이다.

 

 

구현

'방문하지 않은 노드 중 거리값이 가장 작은 노드'를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다. 즉 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 (N−1)×N=O(N2)의 시간이 걸린다.

아래 코드에서 dist[]는 각 노드까지의 최소 거리를 저저장하고, visited[]는 방문 여부를, map[][]은 한 노드에서 다른 노드로의 거리를 저장하고 있다.

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

n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
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 index

# 다익스트라 알고리즘
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()  # 방문X 면서 시작노드와 최단거리인 노드 반환
        visited[now] = True        # 해당 노드 방문처리
        # 해당 노드의 인접한 노드들 간의 거리 계산
        for next in graph[now]:
            cost = distance[now] + next[1]  # 시작->now 거리 + now->now의 인접노드 거리
            if cost < distance[next[0]]:    # cost < 시작->now의 인접노드 다이렉트 거리
                distance[next[0]] = cost


dijkstra(start)

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

 

 

 

2. 성능이 개선된 버전( 우선순위 큐 또는 힙큐 사용)

방문하지 않은 노드의 방문순서를 우선순위를 두어 방문한다.

순차 탐색을 사용할 경우 노드 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다. 이를 개선하기 위해 우선순위 큐를 도입하기도 한다.
거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.
파이썬의 경우 PriorityQueue나 heapq 라이브러리로 우선순위 큐, 최소 힙이 지원되며, C++의 경우 <queue> 라이브러리에서 최대 힙을 지원하는 priority_queue 를 사용할 수 있다. 최대 힙을 최소 힙으로 쓰려면 저장되는 값에 -를 붙여 음수로 만들면 된다.

우선순위 큐에서 사용할 '우선순위'의 기준은 '시작 노드로부터 가장 가까운 노드'가 된다. 따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.

위의 순차 탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리, 노드> 꼴이다.

 

이제 우선순위 큐를 다익스트라 알고리즘에 어떻게 사용하는지 살펴보자. 다익스트라 알고리즘에서 우선순위 가준은 뭘까? 바로 시작 노드와의 거리가 가장 가까운 노드를 의미한다. 따라서 알고리즘을 반복할 때마다 실시간으로 시작노드와 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 활용한다.

 

참고로 기존의 간단한 다익스트라 알고리즘을 구현할 때는 사전에 2가지 종류의 리스트를 먼저 정의하고 진행했다. 첫 번째는 최단 거리를 기록하면서 갱신할 거리 테이블, 두 번째는 방문한 노드인지 처리하고 확인하는 목적의 방문 테이블이였다. 하지만 우선순위 큐를 이용하게 되면 최단 거리를 기록할 거리 테이블만 정의한다. 왜냐하면 우선순위 큐를 이용하게 되면 우선순위 큐가 알아서 가장 최단 거리인 노드를 가장 앞으로 정렬해주기 때문에 기존에 기록한 최단 거리보다 크다면 그냥 무시해주면 된다. 만약 기존에 기록한 최단 거리보다 더 짧은 새로운 최단 거리가 등장하게 되면 해당 거리와 노드를 우선순위 큐에 넣어준다. 자, 이제 그렇다면 우선순위 큐를 활용해서 다익스트라 알고리즘이 어떻게 동작하는지 도식화해서 살펴보자.

첫번째 초기 단계

 

초기 단계

 

 

시작 노드를 1이라고 가정하자. 시작 노드 1에서 1로 가는 거리는 없으므로 0이다. 그리고 시작 노드인 1번에서 1번 노드로 가는 거리는 0 하나이므로 하나의 데이터를 우선순위 큐에 넣어준다.

두 번째 단계

이제 우선순위 큐에 있는 데이터인 (거리:0, 노드:1)을 뽑아서 1번 노드를 탐색하자. 

 

 

두 번째 단계

 

 

위에서 보다 시피 1번 노드와 연결되어 있는 노드들은 2,3,4번 노드들이다. 해당 노드들을 우선순위 큐에 다 집어넣으면 위와 같이 '거리'를 우선순위로 하여 자동 정렬된다. 위 예시에서는 시작노드 1번과 거리가 1로 가장 가까운 4번 노드 데이터가 우선순위 큐안에 가장 앞에 위치한다.(이렇게 해서 시작 노드와 가장 가까운 거리에 있는 노드를 탐색하는 과정을 우선순위 큐가 대신해준다!)

세 번째 단계

다음은 우선순위 큐에 가장 앞에 있는 (거리:1, 노드:4) 데이터를 뽑아서 4번 노드를 탐색한다.

 

 

세번째 단계

 

 

4번 노드와 연결된 노드들은 3,5번노드들이다. 이 때, 중요한 포인트는 연결된 3,5번 노드들과 시작 노드들간의 거리가 이전보다 최단 거리로 업데이트될 경우에만 우선순위 큐에 집어넣는다. 예를 들어 3번 노드는 위 그림에서 보다시피 두 번째 단계에서는 거리가 5였지만 4번 노드를 탐색함으로써 더 최단거리인 거리가 4로 업데이트되었다. 즉, 이럴 때만 우선순위 큐에 집어넣어야 한다는 것이다. 그리고 우선순위 큐 안에서는 거리를 기준으로 가장 가까운 데이터를 다시 앞으로 자동 정렬시켜준다. 

우선순위큐에서 꺼낸 원소의 노드의 거리는 무조건 최소이다. 왜냐하면 다른노드를 통해서 가는길은 무조건 그 원소의 거리보다 멀기 때문이다. 우선순위큐에서 꺼냇기 때문에 최소값임. 그래서 이 단계 이후에 노드4는 수정되지 않는다.

 

방금 설명한 경우와는 반대로, 우선순위 큐에서 꺼낸 데이터의 거리가 기존의 거리 테이블의 거리값보다 클 경우도 있을 수 있다. 이럴 때는 그냥 무시하고 넘어가면 된다. 따라서 우선순위 큐에서 빼낸 노드를 탐색하려 하는데, 해당 노드보다 더 짧은 거리가 거리 테이블에 이미 갱신되어 있을 경우, 이 경우에 대해서는 무시해주고 넘어가면 된다.

import sys
import heapq
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
INF = int(1e9)
distance = [INF] * (n+1)
graph = [[] for _ in range(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            # 시작노드->시작노드 거리 기록
    while q:
        dist, node = heapq.heappop(q)
        # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if distance[node] < dist:
            continue
        # 큐에서 뽑아낸 노드와 연결된 인접노드들 탐색
        for next in graph[node]:
        	if dist[next_node] <next_cost: #이 조건문은 조금이라도 속도를 높히기 위함임. 없어도 큰 차이 없음
                continue
            cost = distance[node] + next[1]   # 시작->node거리 + node->node의인접노드 거리
            if cost < distance[next[0]]:      # cost < 시작->node의인접노드 거리
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))


dijkstra(start)

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

 

 

 

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

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다
• 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를
  기준으로 알고리즘을 수행한다
  • 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다
• 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다
• 각 단계마다 특정한 노드 𝑘를 거쳐 가는 경우를 확인한다
  • 𝑎에서 𝑏로 가는 최단 거리보다 𝑎에서 𝑘를 거쳐 𝑏로 가는 거리가 더 짧은지 검사한다
• 점화식은 다음과 같다

---

플로이드 워셜 알고리즘: 동작 과정 살펴보기

• [초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다

• [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

---

플로이드 워셜 알고리즘 (Python)

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
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(m):
    # 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] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

 

참고: https://techblog-history-younghunjo1.tistory.com/248?category=1014800 https://velog.io/@717lumos/알고리즘-다익스트라Dijkstra-알고리즘  https://freedeveloper.tistory.com/385