벨만포드(Bellman-Ford)
- 그래프 상에 존재하는 두 노드간의 최단거리를 구할 때 사용하는 알고리즘
- Dijkstra 알고리즘과의 차이점은 음의 가중치를 포함할 때 사용가능하다는 점!
- 간선(Edge)의 개수와 노드(Vertex)의 개수에 따라 유동적으로 알고리즘을 사용해야 된다!
전제조건
1. 최단 경로는 사이클을 포함하지 않는다. 따라서 |V| - 1 개의 간선만 사용할 수 있다!
2. 최단 경로가 업데이트 되는 노드가 없어질 때까지 반복해서 구한다!
3. 만약 무한히 업데이트 한다면 이는 조건에 맞지 않으므로 불가능으로 탈출한다!
* 고찰
- 매 라운드마다 모든 Edge를 검사하고, |V| - 1의 라운드 동안 전체 Edge |E|개를 검사하므로
- 시간복잡도는 O(|V||E|), |E|는 최대 V^2
- 공간복잡도는 각 노드 마다 최단 거리를 저장하므로 O(V)
수도코드 및 흐름
1. |V| - 1번의 반복동안
2. 모든 edge를 검사하여, 최단경로를 갱신할 수 있으면 갱신한다!
3. 만약, V 번째에 다시 모든 edge를 검사하여 또 갱신이 된다면
4. 그때는 사이클이 생기므로 불가능한 경우다! ( return False )
5. V번째에 갱신이 안된다면, 사이클이 없는 순환 구조다!
적용
|
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
37
|
import sys
input = sys.stdin.readline
inf = 987654321
n, m = map(int, input().split())
edge = []
for _ in range(m):
f, g, v = map(int, input().split())
edge.append([f - 1, g - 1, v])
# 벨만포드 알고리즘 = 시간복잡도 O(VE), 공간복잡도 O(V)
d = [inf for _ in range(n)]
# 자신은 0
d[0] = 0
cycle = False
# 루프 n-1번에 대해서
for i in range(n - 1):
for j in range(m): # 모든 정점에서
now, next, val = edge[j]
if d[now] != inf and d[next] > d[now] + val: # 최단 경로가 갱신된다면!
d[next] = d[now] + val # 갱신
# 음수 사이클 체크
for j in range(m): # 모든 정점에서
now, next, val = edge[j]
if d[now] != inf and d[next] > d[now] + val:
cycle = True
break
if cycle:
print(-1)
else:
for i in range(1, n):
if d[i] == inf:
print(-1)
else:
print(d[i])
|
cs |
SPFA(Shortest Path First Algorithm)
- SPFA(Shortest Path First Algorithm) : 벨만 포드를 개선하여 음의 가중치에 대한 최단경로를 구하는 알고리즘!
- 사실상 벨만포드는 알고리즘 대회에는 적합하지 않다.. Why? 더 좋은게 있으니까
- 벨만포드는 모든 간선에 대해 업데이트를 진행하지만,
- SPFA는 바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행한다!
- 따라서, 시간복잡도는 최선의 경우 O(|E|), O(|V| + |E|) 최악은 O(|V||E|)
* Why?
- 벨만 포드는 무조건 |V| -1 번 반복하지만, SPFA는 더 이상 업데이트 할 Node가 없다면 한번의 서칭으로 끝난다!
수도코드 및 흐름
1. 시작 Node(s)에 대하여 큐에 삽입한다.
2. Queue에 있는지 없는지는 따로 배열을 만들어서 관리한다! => O(1)
3. Queue에서 맨 앞 Node를 가져와서, 모든 Edge를 검사한다!
4. 만약, 최단거리를 갱신할 수 있으면 갱신한다!
5. Queue에 들어가 있지 않는 Node라면 Queue에 삽입한다!
* 음수 사이클을 확인하려면?
- cycle을 확인하는 배열을 만들어서 Queue에 Node를 삽입할 때 +1 씩 카운트한다!
- 만약, 똑같은 Node에 대해 |V|(정점 개수) 만큼 방문한다면, 음수사이클이다!! = 벨만 포드 참고
적용
|
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
37
38
|
from collections import deque
import sys
input = sys.stdin.readline
inf = 987654321
def SPFA(start):
d = [inf for _ in range(n)] # 최소 비용 거리
on = [False for _ in range(n)] # 큐에 넣었는지 아닌지
cycle = [0 for _ in range(n)] # 무한으로 cycle이 도는지 아닌지
d[start] = 0
on[start] = True
q = deque([start])
while q:
now = q.popleft()
on[now] = False
for next, val in edge[now]: # 다음 간선에대해
if d[next] > d[now] + val: # 갱신할 수 있으면
d[next] = d[now] + val # 갱신
if not on[next]: # 큐에 넣었지 않았으면
cycle[next] += 1 # cycle체크
if cycle[next] >= n: # Node의 개수만큼 큐에 방문했으면
print(-1) # 무한 cycle이므로 답을 구할 수 없음
return
on[next] = True
q.append(next) # 큐에 넣기
for val in d[1:]:
print(-1) if val == inf else print(val)
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
edge[u - 1].append((v - 1, w))
SPFA(0)
|
cs |
참고
벨만 포드 알고리즘
벨만 포드 알고리즘 개념
SPFA
'Developer > Algorithm' 카테고리의 다른 글
| TopologicalSort - 위상정렬 (0) | 2019.04.19 |
|---|---|
| InsertionSort(삽입정렬)이란? (0) | 2019.04.05 |
| Quicksort(퀵정렬)이란? (0) | 2019.04.03 |
| Mergesort(병합정렬)이란? (0) | 2019.04.01 |
