개념

벨먼-포드 알고리즘 - 위키백과, 우리 모두의 백과사전

3가지 길찾기 알고리즘 중 하나인 Bellman-Ford 알고리즘이다. 가중치가 음수이면 작동이 안되는 Dijkstra 알고리즘을 보완할 수 있다.

Bellman-Ford알고리즘은 DP관점의 알고리즘이다.

점화식은 다음과 같다.

$$ D(s, v) = D(s,u) + w(u, v) $$

u를 1부터 n까지, v를 1부터 n까지, 그리고 dist 갱신과정을 n번만큼 반복하므로 시간복잡도가 $O(VE)$이다.

과정

시작 노드와의 거리를 dist로 둔다. 시작노드의 dist는 0, 시작 노드를 제외한 모든 노드의 dist는 inf라고 둔다.
모든 노드에 대하여 dist를 구할 것이다. 모든 노드 1~u, 모든 노드 1~v에 대하여 위의 점화식대로 dist를 초기화 한다.

아래의 Python예제 처럼 처음부터 edge를 돌아도 된다.
위 과정을 모든 노드의 수 n번만큼 반복한다.

< 웜홀 문제 한정 > 모든 노드의 수만큼 반복해서 체크했는데 마지막 n번째 체크에서 갱신되는 dist가 있다면 dist가 계속 감소하는 루프가 있다는 뜻이다. 즉 거리가 무한으로 감소하는 루프가 있다는 뜻.

Python

import sys

I = sys.stdin.readline
inf = 1000000000

def solve():
    n, m, w = map(int, I().split())
    dist = [inf for _ in range(n+1)]
    dist[0] = -1
    dist[1] = 0
    edges = []

    for _ in range(m):
        s, e, t = map(int, I().split())
        edges.append((s, e, t))
        edges.append((e, s, t))

    for _ in range(w):
        s, e, t = map(int, I().split())
        edges.append((s, e, -t))

    cycle = False
    for i in range(n):
        for u, v, w in edges:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if i == n-1:
                    cycle = True
    if cycle:
        print("YES")
    else:
        print("NO")

testcase = int(I())

for _ in range(testcase):
    solve()