[shortest path] 최단 경로 - 다익스트라, 플로이드 워셜

최단 경로 알고리즘이란?

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

최단 경로의 알고리즘은 여러가지 있지만 그 중 다익스트라 최단 경로 알고리즘과, 플로이드 워셜 알고리즘을 기반으로 설명하겠습니다.

 

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

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. 따라서 매 순간 가장 짧은 거리를 선택하므로 그리디 알고리즘이라고 생각하면 됩니다.

그리고 중요한 점은 0보다 작은 음의 간선이 있을 경우 정상적으로 동작하지 않을 수 있습니다.

알고리즘 흐름도

1. 출발 노드를 설정합니다.

2. 최단 거리 테이블을 초기화합니다.

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 것을 선택합니다.

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신합니다.

5. 3번 4번 과정을 방문하지 않은 노드가 없을 때 까지 반복합니다.

이 과정을 통해 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것입니다.

 

다익스트라 코드

import math
import heapq
N,M = 6, 11
start = 1
inputG = [[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]]
graph = [[] for _ in range(N+1)]
for a,b,c in inputG:
    graph[a].append((b,c))

distance = [math.inf] * (N+1)

def dijkstra(start):
    q = []
    
	#시작 노드로 가기위한 최단경로는 0으로 설정하고 (우선순위)큐에 삽입
    heapq.heappush(q,(0, start)) 
    distance[start] = 0

	# 큐가 비어있지 않다면
    while q:
        dist, now = heapq.heappop(q) # 거리가 가장 짧은 노드를 큐에서 꺼냄
        # 현재 노드가 이미 처리된적 있는 노드라면 무시
        # 현재 꺼낸 그 원소의 거리값(dist)이 테이블에 기록되어있는 값 보다 더 크다면 이미 처리된 것
        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] == math.inf:
        print('inf')
    else:
        print(distance[i])

heapq 우선 큐를 이용해 다익스트라 알고리즘을 구현했을 때의 코드입니다.

1.우선 큐에 값을 현재 위치에 대한 데이터를 넣어줍니다.

2.우선 큐에서 현재 위치에 대한 거리와 노드 정보를 꺼내서 값을 확인합니다. (이때 방문했는지를 체크하게 됩니다.)

3. 현재 노드에서 연결된 다른 노드의 거리를 계산하면서 가장 작은 값을 우선 큐에 넣어줍니다.

4. 우선 큐가 비워질 때 까지(방문하지 않은 노드가 없을 때 까지) 반복 합니다.

 

시간복잡도

힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 ElogV 입니다.

E 개의 원소를 우선 큐 순위에 넣었다가 빼는 연산 속도를 가지게 됩니다.

 

 

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다. 다익스트라 같은 경우 가장 최소 값을 선택하는 그리디 알고리즘이였다면 플로이드 워셜은 모든 경우의 수를 빠르게 계산해야하는 다이나믹 프로그래밍 알고리즘입니다.

 

알고리즘 흐름도

점화식 D_ab = min(D_ab, D_ak + D_kb)

각 단계마다 특정한 k 노드를 거쳐 가는 경우를 확인합니다.

a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은 지 확인하면서 dp 테이블을 갱신하게 됩니다.

 

플로이드 워셜 코드

import math
n,m = 4,7
graph = [[math.inf for _ in range(n+1)] for _ in range(n+1)]

for a in range(1,n+1):
    for b in range(1,n+1):
        if a== b :
            graph[a][b] = 0
#그래프 데이터 입력받기
inputG = [[1,2,4],
        [1,4,6],
        [2,1,3],
        [2,3,7],
        [3,1,5],
        [3,4,4],
        [4,3,2]]

for a,b,c in inputG:
        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] == math.inf:
            print("INF")
        else:
            print(graph[a][b], end=" ")
    print()

 

각 단계마다(k) 에서 a에서 b로 가는 경우, a에서 k, k에서 b까지의 거리를 계산한 후 짧은 값을 그래프 테이블에 갱신하게 됩니다. 

시간복잡도

위에 코드에서도 알 수 있듯이 3개의 for문을 이용하므로 시간복잡도는 N^3 입니다.