코드

v, e = map(int, input().split())
INF = int(1e9)
edges = []
    
# 최단 거리 테이블을 무한으로 초기화
dist_table = [INF for _ in range(v+1)]

for _ in range(e):
    
    # c가 음수인 경우가 존재 => 벨만 포드 알고리즘 사용해야 함
    # a : 시작, b : 도착, c : 소요 시간
    a, b, c, = map(int, input().split())
    edges.append((a, b, c))
    
# 벨만 포드 구현
def bellman_ford(start):

    # 시작 지점 최단 거리 테이블만 0으로 설정
    dist_table[start] = 0
    
    for i in range(v):
        
        # 간선에 대한 정보를 s, d, w로 사용
        # start, destination, weight
        for s, d, w in edges:
            
            # s가 INF가 아니고
            # s를 거쳐서 d로 이동하는 거리(dist_table[s] + w)가
            # dist_table[d] 보다 더 짧은경우
            if dist_table[s] != INF and dist_table[d] > dist_table[s] + w:
                
                # 더 짧으니까
                # 최단 거리 테이블을 업데이트 시켜줌
                dist_table[d] = dist_table[s] + w
                
                # i가 v-1과 같아짐 (반복 횟수 == 노드의 개수)
                # 한바퀴를 돌았는데 또 돈다
                # => 싸이클이 존재한다는 의미
                if i == v-1:
                    return False
    return True

# 싸이클이 존재하면 -1
if not bellman_ford(1):
    print(-1)
else:
    
    # 1번 도시 => 다른 모든 노드로 가기 위한 최단 거리 출력
    # 따라서 2부터 시작
    for i in range(2, v+1):
        
        # 경로가 없어도 -1
        if dist_table[i] == INF:
            print(-1)
        else:
            print(dist_table[i])

문제 해설

벨만 포드 알고리즘 문제.

앞서 풀어보았던 문제들과는 달리 가중치에 음수가 존재하는 경우 사용할 수 있는 최단 경로 알고리즘이다.

알고리즘의 작동 순서는 아래와 같다.

  1. 시작 노드에 대한 거리를 0, 나머진 모두 무한으로 설정
  2. 정점의 수 만큼 아래 과정을 반복
    • 현재 노드의 모든 인접 노드를 탐색
    • 기존에 저장된 인접 노드까지의 거리보다 현재 노드를 거치는 거리가 더 짧으면 최단 거리 테이블 갱신
  3. 모든 노드에 대하여 수행한 후에도 거리 갱신이 발생한다면 음의 사이클이 존재함을 의미
    • 자신을 제외한 모든 노드이므로 반복 횟수는 V-1이 됨

i가 v-1과 같아짐 (반복 횟수 == 노드의 개수)

이 포인트가 좀 헷갈릴 수도 있다. 시작 노드를 제외한 나머지 노드에 대하여 탐색을 실시하는데 노드의 개수만큼 반복을 실시하는 경우가 발생한다는 건 시작 노드로 다시 돌아오는 사이클이 발생한다는 의미이므로 결국 무한 탐색이 실시됨을 의미한다. 이 경우, 최단 경로를 구할 수 없다는 의미가 되므로 False를 return 해주고 사이클이 없는 경우 True를 return 해준다.

벨만 포드 알고리즘은 다익스트라 알고리즘이나 플로이드 워셜 알고리즘에 비해서 문제로 자주 출제되지는 않는 것 같다. 하지만 접할 기회가 없는 만큼 잘 숙지하지 못하면 갑작스럽게 마주 했을 때 못 풀 수도 있으므로 많이 연습해서 습득해야겠다.

벨만 포드 알고리즘 참고 블로그

댓글남기기

참고