#2 최단거리 알고리즘 - Bellman-Ford Algorithm

 Dijkstra's Algorithm은 O(ElogV)의 시간복잡도로 한 정점에서 모든 정점으로의 최단거리를 구할 수 있지만

음수간선이 포함된 그래프에서는 사용이 불가능하다.  음수간선이 포함된 그래프에서 최단거리를 구할 수 있으며 음수사이클도 감지 가능한 최단경로 알고리즘인 Bellman-Ford Algorithm에 대해 알아본다.

 

 Bellman-Ford Alogorithm은 시작점에서 모든정점으로의 최단거리를 무한으로 초기화한 후 edge를 순회하며 해당 edge를 통과하는 거리로 최단거리를 갱신해나가는 방식으로 최단거리를 구하는 알고리즘이다.

절차는 다음과 같다.

 

① 먼저 시작점 s로부터의 각 정점까지의 거리를 나타낼 배열 d를 INF(무한)으로 초기화한다.

② d[s]를 0으로 초기화한다 (자기 자신과의 거리는 0이기 때문에)

③ 모든 간선을 순회하며 그 간선을 통과하는 경우의 거리로 최단거리를 갱신해나간다

    ex) d[1] == 0, d[3] == INF   ->  edge : (1, 3, 5)   ->  d[3] = min(d[3], d[1]+5)  ->  d[3] == 5

④ ③을 정점의 수 - 1 회 만큼 반복한다. (그 전에 갱신이 멈추면 반복을 종료한다)

⑤ ④에서 갱신이 멈추지않고 정점의 수 - 1회까지 반복문이 돌아갔을 경우, 한번 더 간선을 순회하여

    최단거리의 갱신이 발생할 경우 음수 사이클이 있어 최단거리를 구할 수 없다는 결과를 얻을 수 있다.

 

Dijkstra's Algorithm 보다도 구현이 단순해서 특별히 주의할 점은 없지만 ④에서 반복문이 정점의 수 - 1만큼 돌아가기 전에도 아무 갱신이 발생하지 않으면 break를 걸어주는 것이 성능 개선에 도움이 된다.

 

알고리즘을 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline
INF = float('inf')


def sol11657():
    n, m = map(int, input().split())
    edge = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edge.append((a-1, b-1, c))
    
    dp = [INF]*n
    dp[0] = 0
    for v in range(n-1):
        check = True
        for s, e, t in edge:
            if dp[s] + t < dp[e]:
                dp[e] = dp[s] + t
                check = False
        if check:
            break
            
    check = False
    for s, e, t in edge:
        if dp[s]+t < dp[e]:
            check = True
            break
    print(-1 if check else '\n'.join(map(conv, dp[1:])))
   

def conv(num):
    return '-1' if num==INF else str(num)


if __name__ == '__main__':
    sol11657()

백준 온라인저지(Baekjoon Online Judge)의 11657번 문제(https://www.acmicpc.net/problem/11657)에 제출한 코드이다.