최단거리

장원재·2024년 12월 23일

알고리즘

목록 보기

6/11

개요

최단거리 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단거리 알고리즘에는 한 지점에서 다른 특정 지점까지의 최단 경롤르 구해야 하는 경우 (다익스트라) & 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우(플로이드 워셜) 등이 있다.

다익스트라

다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 참고로 음의 간선이 없을 때 정상적으로 작동한다.

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

방문하지 않은 노드에서 매번 최단 거리가 가장 짧은 노드를 확인한다는 점에서 그리디 알고리즘으로 볼 수 있다.

동작 과정

출발 노드를 1이라고 가정해보자. 그러면 최단 거리 테이블에서 1번 노드를 0으로 지정한다. 그리고 나머지 노드의 최단 거리는 무한으로 초기화 한다.
최단거리가 가장 짧고, 아직 방문하지 않은1 노드를 선택한다. 그리고 1 노드와 인접한 노드인 2 3 5 노드의 최단 거리는 모두 무한 보다 작으므로 갱신해준다.
테이블에서 방문하지 않은 노드중 가장 짧은 노드인 4 를 선택한다. 그리고 인접한 노드인 3 5 로의 거리를 비교하면, 3 5 노드가 모두 갱신된다. (4 노드를 거쳐서 가는 것이 더 최단 거리이기 때문)
다음으로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 2 5 가 있다. 일반적으로 노드의 번호가 작은 노드부터 선택하므로 2 노드를 선택한다. 이때 2 노드를 거쳐 4 3 노드를 가는 거리는 테이블에 있는 경로보다 더 길기 때문에 갱신하지 않는다.
다음에는 노드 5 가 선택되고 5 노드를 거쳐 3 6 노드로 가는 거리가 더 짧기 때문에 테이블이 갱신된다.
모든 노드들을 방문할 때까지 위 과정을 반복한다.
다익스트라 알고리즘 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

다익스트라 소스코드

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

#노드, 간선 개수
n, m = 6, 11 
#시작 노드
start = 1
#각 노드에 연결되어 있는 노드에 대한 정볼르 담는 리스트 만들기
graph = [[] for _ 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):
    #도달할 수 없는 경우
    if distance[i] == INF:
        print('inf')
    #도달할 수 있는 경우 거리 출력
    else:
        print(distance[i])

다익스트라 시간 복잡도

위의 코드를 기반으로 다익스트라 시간 복잡도는 O(ElogV) 이다. if distance[now] < dist: 를 확인하면 한번 처리된 노드는 더 이상 처리되지 않는다. 그리고 큐에 들어간 노드를 하나씩 꺼내면서, 꺼낸 노드와 연결된 다른 노드를 확인하는 총횟수는 총 최대 간선의 개수(E) 만큼 연산이 수행될 수 있다. 따라서 힙에서 E개의 원소를 모두 넣고 빼는 과정은 O(ElogE) 라 볼 수 있다. 여기서 E는 항상 V^2 보다 작거나 같으므로 O(logV^2) 은 O(logV) 이다. 따라서 시간 복잡도는 O(ElogV) 임을 알 수 있다.

플로이드 워셜

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라 알고리즘 처럼 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 구체적으로 현재 확인하고 있는 노드를 제외하고 N - 1개의 서로 다른 노드 (A,B) 두 쌍을 선택한다. 이후에 A -> 선택 노드 -> B 로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다. 즉, n-1_P_2개의 쌍을 반복해서 확인한다. 이때 O(n-1_P_2) 는 O(N^2) 이라고 볼 수 있기 때문에 시간 복잡도는 O(N^3) 이다.

플로이드 워샬 알고리즘은 다이나믹 프로그래밍 이라는 특징이 있다.
점화식: D_ab = min(D_ab, D_ak + D_kb)

동작 과정

초기에는 자기 자신으로 가는 경로는 0, 연결되어 있는 노드 표시, 연결되어 있지 않다면 무한으로 표시한다. 참고로 D23은 2 노드에서 3 노드로 가는 최단 거리로 위 표에 따르면 7이다.
a -> 선택노드 -> b 중에서 선택 노드를 고른다. 위에서는 선택 노드로 1을 지정했다. 그리고 선택 노드를 제외한 2쌍의 노드를 고른다. 그리고 점화식에 따라서 선택노드를 거쳐서 가는 방법인 a -> 1 -> b과 바로 a -> b로 가는 경로중 더 짧은 경로를 선택해 테이블을 수정해준다.
다음으로는 1 을 제외한 다른 선택 노드를 선택해주고 세부 과정은 동일하다.

플로이드 워셜 소스코드

INF = int(1e9)
#노드의 개수 및 간선의 개수
n, m = 4, 7
#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):
        #도달 할 수 없는 경우
        if graph[a][b] == INF:
            print('inf', end=' ')
        #도달 할 수 있는 경우
        else:
            print(graph[a][b], end=' ')
    print()