[알고리즘] 최단경로 - (Dijkstra(다익스트라)/Floyd-Warshall(플로이드-워셜))

최단 경로 문제

- 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임
- 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

 

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제
  - 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 (single-source shortest path problem) 최단 경로 문제
  - 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
  > 따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 
  > 예를 들어 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면,
  > A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함
3. 전체 쌍(all-pair) 최단 경로: 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

 

다익스트라 알고리즘

• 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• '음의 간선'이 없을 때 정상적으로 동작함
• 1차원 리스트
• 무한 = 10억 = 1e9
• 다익스트라 알고리즘은 위의 최단 경로 문제 종류 중, 2번에 해당
• 하나의 정점에서 다른 모든 정점 간의 각각 **가장 짧은 거리**를 구하는 문제

다익스트라 알고리즘 로직
- 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
- 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사
  - 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
>  다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식에 집중해서 설명하기로 함

- 우선순위 큐를 활용한 다익스트라 알고리즘
  - 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨

1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
        - 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함 (inf 라고 표현함)
        - 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣음 
2.  우선순위 큐에서 노드를 꺼냄
        - 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
        - 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
        - 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
        - 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
          - 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
          - 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
3.  2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

 

간단한 다익스트라 알고리즘

• 시간 복잡도 : O(V^2) → V는 노드의 개수
• 선형적

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

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번 노드로 가는 비용이 c
	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]   #####
	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):
	if distance[i]==INF:
		print("INFINITY")
	else:
		print(distance[i])

 

'''
0 4 3
0 5 10
0 1 7
1 0 7
1 4 2
1 5 6
1 2 4
1 3 10
2 1 4
2 3 2
3 4 11
3 1 10
3 2 2
3 5 9
4 0 3
4 1 2
4 3 11
5 0 10
5 1 6
5 3 9
'''

visited = [False for _ in range(n)]   #방문 배열 선언
cost = [sys.maxsize for _ in range(n)]   #비용 배열 선언
visited[0] = True
cost[0] = 0   #0번 노드를 시작점을 ㅗ설정
length = len(visited)

while False in visited:   #방문하지 않은 노드가 있다면
	checkLoc = -1
	checkValue = sys.maxsize   
	for i in range(length):   #방문하지 않은 지역 중 최솟값 찾기
		if visited[i]==False and cost[i]<checkValue:
			checkLoc = i
			checkValue = cost[i]
	if checkLoc == -1:    #검사할 후보가 없다면 탈출
		break
	visited[checkLoc] = True
	for v1,v2,c in costs:   #경로 완전탐색으로 비용배열 수정
		if v1==checkLoc and visited[v2]==False:
			cost[v2] = min(cost[v2],cost[v1]+c)
		if v2==checkLoc and visited[v1]==False:
			cost[v1] = min(cost[v1],cost[v2]+c)

 

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

• 시간 복잡도 : O(ElogV) → E는 간선의 개수, V는 노드의 개수
• 그래프 문제의 최소 신장 트리 문제에도 적용됨
• 우선순위 큐 : 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식 사용

'''입력 예시
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 []
1 [(2,2),(3,5),(4,1)] 
2 [(3,3),(4,2)] 
3 [(2,3),(6,5)]
4 [(3,3),(5,1)]
5 [(3,1),(6,2)]
6 []
'''

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

n,m = 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 = []   #####
	heapq.heappush(q, (0,start))   ##### q = [(0,1)]
	distance[start] = 0
	while q:
		dist, now = heapq.heappop(q)   #####
		if distance[now] < dist:   ##### 현재 노드가 이미 처리된 적 있는 노드라면 무시
			continue   #####
		for j in graph[now]:
			cost = dist + j[1]   #####distance[now] 대신 dist
			if cost<distance[j[0]]:
				distance[j[0]] = cost
				heapq.heappush(q, (cost,i[0]))   #####

dijkstra(start)

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

#패스트캠퍼스
mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq

def dijkstra(graph, start):
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if distances[current_node] < current_distance:
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances
    
    dijkstra(mygraph, 'A')

시간 복잡도

- 위 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침
  - 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
  - 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정
  
- 각 과정별 시간 복잡도
  - 과정1: 각 노드는 최대 한 번씩 방문하므로 (첫 노드와 해당 노드간의 갈 수 있는 루트가 있는 경우만 해당), 그래프의 모든 간선은 최대 한 번씩 검사
    - 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림, E 는 간선(edge)의 약자

  - 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림
    - 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임
    - 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 $ O(log{E}) $ 가 걸림
      - 따라서 해당 과정의 시간 복잡도는 $ O(Elog{E}) $ 
    
### 총 시간 복잡도
  - 과정1 + 과정2 = O(E) + $ O(Elog{E}) $  = $ O(E + Elog{E}) = O(Elog{E}) $
  
### 참고: 힙의 시간 복잡도
- depth (트리의 높이) 를 h라고 표기한다면,
- n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로  h=log2n  에 가까우므로, 시간 복잡도는  O(logn)

 

최단 경로 출력
- 탐색할 그래프의 시작 정점과 다른 정점들간의 최단 거리 및 최단 경로 출력하기

import heapq

# 탐색할 그래프와 시작 정점을 인수로 전달받습니다.
def dijkstra(graph, start, end):
    # 시작 정점에서 각 정점까지의 거리를 저장할 딕셔너리를 생성하고, 무한대(inf)로 초기화합니다.
    distances = {vertex: [float('inf'), start] for vertex in graph}

    # 그래프의 시작 정점의 거리는 0으로 초기화 해줌
    distances[start] = [0, start]

    # 모든 정점이 저장될 큐를 생성합니다.
    queue = []

    # 그래프의 시작 정점과 시작 정점의 거리(0)을 최소힙에 넣어줌
    heapq.heappush(queue, [distances[start][0], start])

    while queue:
        
        # 큐에서 정점을 하나씩 꺼내 인접한 정점들의 가중치를 모두 확인하여 업데이트합니다.
        current_distance, current_vertex = heapq.heappop(queue)
        
        # 더 짧은 경로가 있다면 무시한다.
        if distances[current_vertex][0] < current_distance:
            continue
            
        for adjacent, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # 만약 시작 정점에서 인접 정점으로 바로 가는 것보다 현재 정점을 통해 가는 것이 더 가까울 경우에는
            if distance < distances[adjacent][0]:
                # 거리를 업데이트합니다.
                distances[adjacent] = [distance, current_vertex]
                heapq.heappush(queue, [distance, adjacent])
    
    path = end
    path_output = end + '->'
    while distances[path][1] != start:
        path_output += distances[path][1] + '->'
        path = distances[path][1]
    path_output += start
    print (path_output)
    return distances

# 방향 그래프
mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

print(dijkstra(mygraph, 'A', 'F'))

 

 

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 2차원 리스트
• 시간 복잡도 : O(N^3)
  • K번 단계에 대한 점화식
  • D_{ab} = min(D_{ab}, D_{ak} + D_{kb})
  • A에서 B로 가는 최단거리 = 최솟값(A에서 B로 가는 최소 비용, A에서 K를 거쳐 B로 가는 비용)

INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1,n+1):   #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
	for b in range(1,n+1):
		if a==b:
			graph[a][b] = 0

for _ in range(m):
	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("INFINITY", end=' ')
		else:
			print(graph[a][b], end=' ')
	print()

 

'''
0 4 3
0 5 10
0 1 7
1 0 7
1 4 2
1 5 6
1 2 4
1 3 10
2 1 4
2 3 2
3 4 11
3 1 10
3 2 2
3 5 9
4 0 3
4 1 2
4 3 11
5 0 10
5 1 6
5 3 9
'''

values = [2**31-1 for i in range(n)]   #비용 배열
visited = [False for i in range(n)]   #방문 배열
start = 0   #0번 노드를 시작점으로 설정
visited[start] = True
values[start] = 0

while False in visited:   #방문하지 않은 노드가 있다면
	for i in costs:   #노드의 완전탐색으로 비용배열의 거리 값 최소화
		if(visited[i[1]]==False and i[0]==start):
			values[i[1]] = min(values[i[1]], i[2])
		if(visited[i[0]]==False and i[1]==start):
			values[i[0]] = min(values[i[0]], i[2])
	refer = 3**31-1
	for i in range(n):   #방문하지 않은 노드 중 최소 비용 노드 위치 탐색
		if(visited[i]==False and values[i]!=0):
			refer = min(refer, values[i])
	answer = answer + refer
	for i in range(n):   #해당 노드 방문 여부 체크
		if(visited[i]==False and values[i]==refer):
			visited[i]=True
			start = i
			break