*참고 - 나동빈 유튜브
알고리즘 - 다익스트라 알고리즘(Dijkstra)
*참고 저서 <이것이 취업을 위한 코딩테스트다> 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이
gae-gi-da.tistory.com
다익스트라 알고리즘은 이전 포스트에서 말했듯이,
모든 간선의 가중치가 양수일 때만 적용이 가능하다.
현실의 상황에서는 간선의 가중치, 즉 거리가 음의 시간이 소요되는 것이 불가능하기에
다익스트라 알고리즘이 언제나 적용이 가능하고 실제로 많은 내비게이션 등의 시스템에서
근간이 되는 알고리즘이기도 하다.
다만 수학적으로는 음의 간선도 충분히 존재할 수 있다.
특히 아래처럼 간선들의 총합이 음수가 되는 사이클이 존재할 경우, 해당 노드와 연결된 모든 노드에 대한 거리가
음의 무한대가 돼버린다.
벨만-포드 알고리즘의 특징은 음수 간선이 포함된 경우에도 사용할 수 있으며
음수 간선의 순환(사이클)을 감지할 수 있다는 것이다.
다만 다익스트랑 알고리즘의 수행시간인 O(ElogV)에 비해
O(VE)로 좀 더 느리다.
벨만 포드 알고리즘의 과정은 다음과 같다.
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 N-1번 반복한다.
1) 전체 간선 E를 하나씩 확인한다.
2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
(만약 3번 과정을 한 번더, 즉 n번째 반복했을 시에 데이터 갱신이 발생한다면,
이는 음수 간선 순환이 존재한다는 말과 같다.)
코드는 다음과 같으면 보다시피 노드의 개수 n과 간선의 개수 m의 곱만큼
반복문이 진행된다는 것을 확인할 수 있다.
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int, input().split())
edges = []
dist = [INF] * (n+1)
for _ in range(m):
a,b,c = map(int,input().split())
edges.append((a,b,c))
def bf(start):
dist[start] = 0
for i in range(n):
for j in range(m):
cur = edges[j][0]
next_node = edges[j][1]
cost = edges[j][2]
if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
dist[next_node] = dist[cur] + cost
if i == n-1:
return True
return False
is_negative_cycle = bf(1)
if is_negative_cycle:
print('-1')
else:
for i in range(2,n+1):
if dist[i] == INF:
print('-1')
else:
print(dist[i])
'대딩 기록(~22.01) > 알고리즘 공부노트' 카테고리의 다른 글
알고리즘 - 병합 정렬, 퀵 정렬(Merge sort, Quick sort) (0) | 2021.07.30 |
---|---|
알고리즘 - 선택정렬, 버블정렬, 삽입정렬 (Selection sort, Bubble sort, Insertion sort) (0) | 2021.07.30 |
알고리즘 - 플로이드 와샬 알고리즘(Floyd Warshall Algorithm) (0) | 2021.07.20 |
알고리즘 - 다익스트라 알고리즘(Dijkstra) (0) | 2021.07.20 |
알고리즘 - 배낭문제 (Knapsack problem) (백준 12865 - 평범한 배낭) (0) | 2021.07.15 |