[알고리즘 개념] 최단경로 알고리즘 - 다익스트라, 플로이드 워셜, 벨만 포드

 

다익스트라 알고리즘

특정 노드에서 다른 노드(One To Any)로 가는 각각의 최단 경로 구하기

모든 vertex 사이의 edge의 cost는 음수가 아니어야 한다

-> 그렇기 때문에 실제 길 찾기 알고리즘으로 쓰인다

 

"가장 비용이 적은 vertex를 선택하여 경로 삼는 방식 -> 가장 작은 비용이 적은거를 기반으로 다음 노드를 선택하면 그 다음 노드도 결국 비용이 작은 것이다!!! " 

따라서 알고리즘 분류를 한다면 greedy 알고리즘 에 속한다

 

준비 사항

• 최단 거리 배열 - 각 idx는 vertex를 가리키고 출발점에서 해당 vertex까지의 최단 거리 / 각 vertex에 대한 현재까지의 최단 거리
• visited 배열 - 방문했는지 체크

 

과정

1. 최단 거리 배열을 1e9 로 초기화
2. 최단 거리 배열의 출발 vertex idx를 0으로 설정 / visited 처리
3. 출발 vertex와 연결되어 있는 vertex 와의 cost를 최단 거리 배열에 넣기 ( 어디로 가느냐의 문제이고 어디를 간것은 아니기 때문에 visited 처리는 하지 않는다 )
4. 아직 방문하지 않은 vertex 중에서 최단거리가 가장 짧은 vertex 선택 ( 가장 짧은 노드를 기반으로 쌓아 올리면 또 최단거리겠지? )
5. 해당 vetex를 거쳐서 다른 vertex로 가는 비용 계산 -> 최단 거리 배열 갱신 / visited 처리 (쌓아올렸다!) 
6. 4번과 5번을 반복

 

구현 - 방법1

graph를 통해 모든 vertex들을 탐색하며 나아가는 방법

(양방향 그래프로 data가 주어졌다고 가정!)

INF = int(1e9)

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

start = int(input())

# 어떻게 보면 양방향 그래프라고 할수 있을까?
graph = [[] for _ in range(n+1)]

# graph - 양방향 그래프
# 1 -> 2인 경우) graph[1] 에 2가 있고, graph[2] 에 1이 있다
for i in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


for g in graph:
    g.sort(key= lambda x:(x[1], x[0]))


visited = [False] * (n+1)
visited[0] = True

dist = [int(1e9)] * (n+1)
dist[start] = 0

while (False in visited):

    visited[start] = True

    for adj_node in graph[start]:
        idx, cost = adj_node
        if visited[idx] is False and dist[idx] > dist[start] + cost:
            dist[idx] = dist[start] + cost
    
    # 현재 방문하지 않은 vertex 중에서 가장 최단 거리인 vertex를 찾아주는 것 -> 이 부분에서 시간이 선형적으로 찾으면서 오래걸린다
    min = int(1e9)
    for i in range(1, n+1):
        if visited[i] is False and min > dist[i]:
            min = dist[i]
            start = i



for i in range(1, n+1):
    if dist[i] == INF:
        print("INFINITY")
    else:
        print(dist[i])

구현 - 방법2

이것이 코테다(저자 나동빈) 책에 나온 코드이다.

graph가 1방향이라고 가정 시

import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미 = 10억

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

# 모든 edge 입력 받기
for i in range(m):
    a, b, c = map(int, input().split())
    #a에서 b node로 가는 비용이 c라는 이야기
    graph[a].append((b,c))

# 방문하지 않은 Node들 중에서 가장 최단 거리가 짧은 Node 번호 -> 이곳에서 시간이 더 걸린다!! 최적화 필요
def get_smallest_node():  
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if visited[i] is False and distance[i]<min_value:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 Node 기준으로 초기화
    distance[start] = 0
    visited[start] = True
    # 시작 Node에 붙어 있는 node들과의 distance를 업데이트
    for j in graph[start]:
        distance[j[0]] = j[1]
    
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 Node와 연결된 모든 Node들을 비교하여 만약에 cost가 더 낮다면 distance에 넣어주기
        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):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

시간 복잡도 

총 N개의 vertex가 있다고 가정, 모두 연결되었을 때, 

각 graph[node_idx] 에는 n-1개의 element가 있음

해당 element들을 모두 검사하기 위해서는 (n-1)^2 이므로 -> O(n^2)의 시간이 소요

즉, 10000개가 넘어가면 시간 초과로 문제해결 어렵다!

 

 

개선된 구현

가장 최소의 거리를 가지고 있는 vertex를 찾는 데에 시간이 걸리니 해당 부분을 

자료구조를 통해서 최적화 시켜주어야 한다

O(ElogV) 로 최적화 가능 (E- edge V-vertex)

 

우선순위 큐 Priority Queue

우선순위의 개념을 큐에 도입한 자료구조 : 우선순위가 가장 높은 것이 먼저 pop되어 나간다

파이썬 모듈

• PriorityQueue
• heapq - 더 빠르게 동작

heapq

default는 최소힙(우선순위 값이 가장 낮은 데이터가 먼저 삭제)이다

제일 첫번째로 입력받은 객체의 우선순위를 기준으로 우선순위 큐를 구성

따라서 최대힙으로 표현하고 싶다면 우선순위를 모두 음수로 표기하는 방법이 있다

• heapq.heappush(heap, item) - heap을 유지하면서 item을 heap에 넣는다
• heapq.heappop(heap) - heap을 유지하면서 heap에서 우선순위가 가장 낮은 항목이 pop되고 삭제된다 (비어있으면 IndexError) heap[0] 은 우선순위가 가장 낮은 항목
• heapq.heapreplace(heap, item) - 우선순위가 가장 낮은 항목을 팝하여 반환하고 새로운 item을 push 한다 ( heppop하고 heappush 하는 것보다 더 효율적 )
• heapq.heapify(list) - list를 힙으로 변환

한개의 vertex를 heapq에 넣는 시간은 O(logN)

따라서 heap을 사용하여 N개의 vertex를 모두 넣고 O(NlogN)

N개의 vertex를 모두 heap에서 뺀다면 O(NlogN)이므로

총 O(2NlogN)으로 빅오 표기법에 따르면 O(NlogN)이 된다

 

이를 리스트를 통해 만들게 된다면 O(N^2)이므로 시간이 훨씬 단축된것을 확인할 수 있다

 

 

파이썬 heapq document

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.2 문서

구현

graph가 양방향 그래프 인 경우

import heapq
INF = int(1e9)

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

start = int(input())

# 어떻게 보면 양방향 그래프라고 할수 있을까?
graph = [[] for _ in range(n+1)]

# graph - 양방향 그래프
# 1 -> 2인 경우) graph[1] 에 2가 있고, graph[2] 에 1이 있다
for i in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

visited = [False] * (n+1)
visited[0] = True

dist = [int(1e9)] * (n+1)
dist[start] = 0

q = []
heapq.heappush(q, (0, start))
visited[start] = True

while True:

    if len(q) == 0:
        break

    distance, vertex = heapq.heappop(q)

    for adj_node in graph[vertex]:
        idx, cost = adj_node
        if visited[idx] is False and dist[idx] > dist[start] + cost:
            dist[idx] = distance + cost
            visited[idx] = True
            heapq.heappush(q, (dist[idx], idx))


for i in range(1, n+1):
    if dist[i] == INF:
        print("INFINITY")
    else:
        print(dist[i])

 

시간복잡도

heap 자료구조를 이용한 우선순위 큐를 만들어서

각 vertex까지의 최소 거리에 대한 정보를 우선순위 큐에 담아서 

기존에 O(V) 걸리는 것을 O(ElogV)에 찾을 수 있다

 

 

 

플로이드 워셜 알고리즘

위의 다익스트라가 One To Any 로 가는 최단 거리를 구하는 것이라면

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로(Any To Any) 알고리즘이다 

 

"A부터 B까지 가는데에 최소라면 그것의 중간인 C까지 가는 A에서 C까지 가는 것도 최소이다"

따라서 알고리즘 분류를 한다면 Dynamic Programming 이다

 

정의만 보아도 일단 1차원으로 답을 구할 수 없고 모든 경우를 다 구해야 하므로 2차원으로 구해야함을 캐치할 수 있다

 

현재 확인하고 있는 vertex(C)를 제외하고 

모든 vertex 중에서 (A,B) 쌍을 선택한다

 

점화식을 세운다면

Dist[A][B] = min(Dist[A][B], Dist[A][C] + Dist[C][B])

A에서 B로 바로가는 cost가 C를 거쳐가는 cost와 비교하는 것이고 모든 vertex들을 돌기 때문에 모든 경우를 체크 가능

 

플로이드 워셜 알고리즘에서는 굳이

visited와 최단 거리를 저장하는 dist 배열을 따로 둘 필요가 없다

graph 에서 모두 처리 가능하다

• graph[i][i] = 0 으로 처리 -> 같은 곳에서 같은 곳으로 가는 최단 거리는 0
• cost가 있는 경로 외의 경로 = 1e9  -> min에 영향받지 않는다

INF = int(1e9)

n, m = map(int, input().split())

graph = [[INF]*(n+1) for i in range(0, n+1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

for i in range(1, n+1):
    graph[i][i] = 0

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


print(graph)