백준 / 11657 / 타임머신 / python

def bellman(start):
    dist[start] = 0

    for i in range(1, n+1):
        for j in range(m):
            node, next_node, dis = graph[j]

            if dist[node] != 1e9 and dist[next_node] > dist[node] + dis:
                dist[next_node] = dist[node] + dis

                if i == n:
                    return True
    return False

n, m = [int(v) for v in input().split()]

dist = [1e9] * (n+1)
graph = []

for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((a,b,c))

check_negative = bellman(1)

if check_negative:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == 1e9:
            print(-1)
        else:
            print(dist[i])

벨만-포드 알고리즘

벨만-포드 알고리즘은 간선 중에 음수가 있을 시 사용하는 알고리즘이다.
다익스트라 알고리즘으로 음수 가 있는 간선에서의 최단거리를 구하게 되면 음수에 의해 계속해서 수치가 작아지게되어 해당 경로에서 무한 루프에 갇히게 될 수가있다.

벨만-포드 알고리즘은 최단경로를 구하면서도 이러한 무한 루프에 갇히는 경로가 있는지도 파악할 수 있는 지도 파악할 수 있는 알고리즘이다.
다만 모든 간선에 대해 노드의 갯수 만큼 탐색하므로 시간 복잡도는 O(VE) (v= 노드 수, e= 간선 수)의 시간 복잡도를 갖는다. 다익스트라 알고리즘의 시간 복잡도인 O(ElegV)보다는 큰 수치이기 때문에 간선에서 음수가 있을 때만 사용하는것이 적합하다.

벨만-포드 알고리즘은 우선 간선 정보를 graph 형식으로 저장하지 않고 위 코드 처럼 입력 받는 간선 정보를 그대로 저장한다.

그 다음 노드의 갯수만큼 간선 정보를 반복해서 탐색한다. 이렇게 해서 최단경로를 구하게 된다.
마지막까지 간선이 수정된다면 무한 루프(계속 해서 작아지는) 경로가 있는 경우가 되므로 true를 반환해주고 그렇지 않은경우 false를 반환해줌으로서 무한 루프 경로가 있는지 확인할 수 있다.