[TIL] 최단 경로 알고리즘 - 벨만 포드 알고리즘

벨만 포드 알고리즘

• 최단 경로 알고리즘 중 하나로 가중치가 음수인 경우 적용 가능하다.
• 다익스트라보다 시간복잡도가 느리다.
• 음수 사이클 존재의 여부를 파악할 수 있다.

 

 

관련문제

 

11657번: 타임머신 (acmicpc.net)

11657번: 타임머신

처음 문제를 접근 할 때 벨만 포드 알고리즘을 몰랐기 때문에

다익스트라 알고리즘으로 접근하였다.

3개의 테스트 케이스를 분석한 뒤에

나름대로(?)

가중치가 음수인 경우를 따로 분리하여 코드를 짰다.

음수인 경우만 체크했을 때에는 12%에서 오답이 떴고

음수의 절댓값까지 체크했을 때에는 40%에서 오답이 떴다.

import sys
import math
import heapq
INF = int(1e9)
input= sys.stdin.readline

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

bus=[[] for _ in range(n+1)]

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

def dijkstra(start):
    dist=[INF]*(n+1)
    dist[start] = 0
    q=[]
    
    heapq.heappush(q, (0,start))
    
    while q:
        time , city = heapq.heappop(q)
        
        if dist[city] < time:
            continue
        
        for time2, next in bus[city]:
            total = time2+time
            
            if dist[next] > total:
                if total <0 :
                    return -1
                dist[next] = total
                heapq.heappush(q, (total, next))
    return dist

if n ==1 and b==1 and c>=0:
    print(c)    
else:      
    rst = dijkstra(1)

    if rst == -1:
        print(rst)
    else:
        for i in range(2, len(rst)):
            if rst[i] ==INF:
                print(-1)
            else:
                print(rst[i])

테스트 케이스는 다 통과했지만 계속 실패를 했고

결국 풀이를 찾아보며 음수 가중치의 순환이 있을 경우

벨만 포드 알고리즘을 사용할 수 있다는 것을 알고

다시 코드를 짜 보았다.

 

import sys
import math
import heapq
INF = int(1e9)
input= sys.stdin.readline

# 벨만포드 알고리즘 

def bf(start):
    dist[start] = 0
    
    for i in range(n):
        for j in range(m):
            cur = edges[j][0]
            next = edges[j][1]
            cost = edges[j][2]
            
            if dist[cur] != INF and dist[next] > dist[cur]+cost:
                dist[next] = dist[cur] +cost
                if i == n-1:
                    return True
    return False



n,m = map(int, input().split())
dist=[INF]*(n+1)
edges=[]
for _ in range(m):
    a,b,c = map(int, input().split())
    edges.append((a,b,c))
    
cycle = bf(1)

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

벨만 포드 알고리즘은 시작 정점에서 다른 모든 정점까지 최단거리를구한다.

만약 그래프 정점의 개수가 n개라면 시작 정점에서 다른 특정한 정점까지 도달하는데 거쳐가는 최대 간선의 개수는

n-1개이기 때문에 n번째에 최단거리 값이 갱신된다면 사이클이 존재함으로 판단할 수 있음을 이용한다.

 

따라서 정점의 개수 만큼 모든 간선을 고려하여 최단거리를 갱신하면서

사이클이 존재할 경우 False를 리턴하게 하였다.