이 포스팅은 나동빈 님의 www.youtube.com/watch?v=Ppimbaxm8d8 벨만포드 알고리즘 강의를 참고하였습니다.
개념
벨만 포드 알고리즘은 다익스트라 알고리즘과 비슷하지만 음의 간선이 있는 경우 사용할 수 있다는 점에서 큰 장점을 지닙니다. 또한 음의 간선 사이클이 존재할 경우 이를 검출할 수도 있는 장점을 지니고 있습니다.
이러한 장점을 가짐과 동시에 O(ElogV)라는 시간복잡도를 지닌 다익스트라 알고리즘과 달리 O(VE)의 시간 복잡도를 지닌다는 단점도 존재합니다.
과정은 다음과 같습니다.
1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화 합니다.
3. 전체 간선 E를 확인합니다.
4. 각 간선을 확인하며 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 계산합니다.
5. 위의 3, 4번 과정을 n-1번 반복을 합니다.
6. 만약 n번째에서도 최단 거리 테이블이 갱신된다면 음의 간선 순환 사이클이 존재한다는 것입니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
edges = []
dist = [INF] * (1+n)
for i 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
negative_circle = bf(1)
if negative_circle:
print(-1)
else:
for i in range(2, n+1):
if dist[i] == INF:
print(-1)
else:
print(dist[i])
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 크루스컬 알고리즘 (Python) (0) | 2020.12.31 |
|---|---|
| 사이클 판별 알고리즘 (Python (0) | 2020.12.31 |
| 서로소 집합 알고리즘 (Python) (0) | 2020.12.30 |
| 다익스트라 알고리즘 (Python) (0) | 2020.12.22 |
| 편집거리 알고리즘 (Python) (0) | 2020.12.22 |