[ 벨만 - 포드 ] 알고리즘

 

 

1.  개념

     

     벨만 - 포드 알고리즘 : 그래프에서 최단 거리를 구하는 알고리즘

     특징

      - 음수 가중치 에지가 존재해도 수행 가능

      - 그래프 내 음수 사이클의 존재 여부 판단 가능  ->  사이클 존재 여부 파악하는 문제에서 사용 

     시간 복잡도 : O(VE)  ->  V : 노드 수, E : 에지 수

 

 

2.  구현

      

      (1) 초기 설정

           - 에지 리스트 생성 -> 그래프 구현

           - 최단 거리 리스트(정답 리스트) 생성 -> 시작 노드는 0으로, 나머지 노드는 무한으로 초기화

      

      (2) 최단 거리 업데이트

           업데이트 반복 횟수 : ( 노드 수 - 1 )회

           한번 업데이트 할 때마다 모든 에지를 방문하며 업데이트 조건을 만족하면 최단 거리 값을 변경해준다

           업데이트 조건 ( s: 출발 노드, e: 도착 노드, w: 가중치 )

            - D[s] != 무한

            - D[e] > D[s] + w

        

     (3) 사이클 존재 여부 판별

           업데이트 과정을 한번 더 반복했을 때 최단 거리에 변동이 생긴다면 사이클이 존재함을 의미한다

 

 

3.  문제

 

# 1  타임머신으로 빨리 가기 - 백준 11657번

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

edge = []  # 에지 리스트
D = [sys.maxsize for _ in range(n+1)] # 최단 거리 리스트

# 시작 노드의 최단 거리 값 0으로 초기화
D[1] = 0

for i in range(m):
    s, e, w = map(int, input().split())
    edge.append((s, e, w))

# 업데이트
for i in range(n-1):
    for s, e, w in edge:
        if D[s] != sys.maxsize and D[e] > D[s] + w:
            D[e] = D[s] + w

# 사이클 존재 여부 판별
ans = True
for s, e, w in edge:
	# 업데이트 한번 실행했을 때 최단 거리 값에 변동이 생긴다면
    if D[s] != sys.maxsize and D[e] > D[s] + w:
        ans = False

# 사이클이 존재하지 않을 때
if ans:
    for i in range(2, n+1):
    	# 끝 노드에 도달하지 못했다면
        if D[i] == sys.maxsize:
            print(-1)
        else:
            print(D[i])

# 사이클이 존재할 때
else:
    print(-1)

 

 

 

# 2  오민식의 고민 - 백준 1219번

https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

 

import sys
input = sys.stdin.readline

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

edge = [] # 에지 리스트
D = [-sys.maxsize for _ in range(n)] # 최단 거리 리스트

# 에지 리스트로 그래프 구현
for i in range(m):
    s, e, w = map(int, input().split())
    edge.append([s, e, w])

# 도시 수익 리스트
money = list(map(int, input().split()))

# 시작 노드 초기화 -> 가만히 있어도 수익을 얻을 수 있으므로 money[start]으로 초기화
D[start] = money[start]

# 에지의 가중치 초기화 -> 해당 에지를 방문할 때 최종적으로 얻게 되는 수익 or 손해
# 도시 수익 - 교통비
for i in range(len(edge)):
    edge[i][2] = money[edge[i][1]] - edge[i][2]

# 업데이트
for i in range(n-1):
    for s, e, w in edge:
        if D[s] != -sys.maxsize and D[e] < D[s] + w:
            D[e] = D[s] + w

# n = 1라도 업데이트 한번 돌리기
if n == 1:
    k = 1
else:
    k = n-1
for i in range(k):
    for s, e, w in edge:
    	# 사이클이 존재할 경우
        if D[s] != -sys.maxsize and D[e] < D[s] + w:
        	# 도착 노드의 최단 거리 값 무한으로 보내기
            D[e] = sys.maxsize


# 끝 노드에 도착하지 못했을 경우
if D[end] == -sys.maxsize:
    print("gg")
else:
	# 끝 노드의 최단 거리 값이 무한일 경우
    if D[end] == sys.maxsize:
        print("Gee")
    else:
        print(D[end])

 

이 문제는 최소값이 아닌 최댓값을 구하는 문제이므로

처음에 정답 리스트 값을 sys.maxsize 대신 -sys.maxsize로 지정했고

업데이트 조건을 거꾸로 뒤집어줬다

 

끝 노드의 리스트 값이 -sys.maxsize일 경우 최종적으로 끝 노드에 도달하지 못했음을 의미하므로 gg를 출력하도록 했다

 

양수 사이클이 존재하는 동시에 그 사이클이 끝 노드에 영향을 줄 때 Gee를 출력하고

최종적으로 끝 노드에 도달하는 동시에 사이클이 존재하지 않거나 사이클이 끝 노드에 영향을 주지 않을 때

정답 리스트에 저장되어 있는 값을 출력하도록 했다

 

양수 사이클이 끝 노드에 영향을 주는지 판별하기 위해 업데이트를 한번만 하는 것이 아니라

(노드-1)만큼 다시 반복해줬다

 

마지막에 양수 사이클이 끝 노드에 영향을 주는지 판별하는 부분에서 애를 많이 먹었는데

그 부분은 교재를 참고했다...

세은이는 사이클에 해당하는 노드를 bfs에 넣고 끝 노드에 도달하는지 확인했다고 한다

그것도 확실히 판별할 수 있는 좋은 방법인 것 같다..!!

 

 

 

 

 

 

마지막에 많이 애먹었지만 처음으로 플래티넘 문제를 얼추 풀어본 것 같아서 기분이 좋당 히히