벨만 포드 알고리즘(Bellman-Ford Algorithm)

벨만 포드 알고리즘이란? 

단일 소스 꼭짓점에서 다른 모든 꼭짓점까지의 최단 경로를 계산하는 알고리즘이다.

다익스트라와 같은 문제에 대한 알고리즘보다는 느리지만, 

가중치 중 일부가 음수인 그래프를 처리할 수 있기 때문에 더 다용도적이다

이 알고리즘은 알폰소 심벨(1955)이 처음 제안했지만, 대신 1958년과 1956년에 각각 발표한 리처드 벨먼과 레스터 포드 주니어의 이름을 따서 명명되었다.[2] 에드워드 F 무어는 1959년에 이 알고리즘의 변형을 발표했으며, 이러한 이유로 벨먼-포드-무어 알고리즘이라고도 불린다.

---

다시, 이전에 설명한 다익스트라 알고리즘과 (모든 꼭짓점까지의 최단경로를 구하기에)비슷 하지만 차이점으로는

가중치(비용)이 음수가 가능하다. 

 

여기서 의문이 생길 수 있다.  

" 가중치가 음수가 되다고하면 어쩌라고,, 그럼 음수가 최소가 되니 다익스트라로 돌리면 되는거 아냐? "

아래 그림을 보자 

 

알겠는가?

 

는 사실 이렇게 보면 다익스트라랑 똑같기만 하구만 라고 생가할 것이다. 

차이점은 사실  이러하다. 

 

 

위 그림에서 가장 짧은 길은 어디인가? 

바로 1 4 5 6 순이다.

 

 

그런데 만약 6-> 1로 가는 음수의 길이 있다면????!!!!!

 

1456 1456 1456 을 반복하다가는 음의 무한대로 간다..

다익스트라의 경우 무한루프에 빠진다.

그러나 벨만포드 알고리즘은 해당 nagative cycle(무한음수만드는 싸이클)을 찾을 수 있다.

고로 작동 방식은 비슷하다. 그러나 위에서 말했다시피 다른점은 음수가 가능하다는것.

(그래서 뭐 어쩌라고!!)

다익스트라의 경우 그리디 알고리즘과 같이 작동하지만 벨만포드는 DP에 가깝다.

---

 

 

 벨먼-포드 알고리즘의 작동방식은 이러하다

1. 먼저 시작 꼭짓점에서 다른 모든 꼭짓점까지의 경로 길이를 비교함평으로써 작동한다.

2. 그런 다음 이전에 비교된 경로보다 더 짧은 새 경로를 찾아 이러한 추정치를 반복적으로 완화한다.

3. 마지막으로 음의 사이클을 점검한다. 

 

아래 코드를 통해 이해해보자 

 

11657번: 타임머신

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

n, m = map(int, input().split())
edges = []
dist = [INF]*(n+1)

for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u,v,w))

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

n_c = bf(1)

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

 

그림참고) https://commons.wikimedia.org/wiki/File:Shortest_path_Dijkstra_vs_BellmanFord.gif