[알고리즘] 벨만-포드 알고리즘

벨만포드 알고리즘

최단경로라는것은 같은정점을 두번 지날일이 없기때문에 최단 경로의 간선개수는 최대 V-1개이다. 따라서 루프를 V-1번 (V는 노드의수) 돌리는데(최악의 경우까지 모두 커버가 가능), k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어 ( 이렇기 때문에 음의순환을 찾을때 한번더 수행하는것 )

• 음수간선이 포함된 상황에서 최단거리 찾기
• 모든간선이 양수일때는 다익스트라를 사용하면 된다.
• 음수 간선의 순환이 발생하는 경우, 최단거리가 음의 무한인 노드가 발생한다. (계속해서 줄일수있으니까 무한대로 순환)

 

간선에 관하여 최단 경로문제는 다음과 같이 분류된다.

1. 모든 간선이 양수인 경우 ( 다익스트라, 플로이드 와샬)
2. 음수 간선이 있는 경우 ( 벨만-포드 )
   1. 음수 간선 순환이 있는 경우
   2. 음수 간선 순환이 있는 경우

벨만포드 최단경로 알고리즘은 음의 간선이 포함된 상황에서도 사용가능하다.

또한 음수 간선의 순환을 감지할 수 있다.

 

기본 시간복잡도 : O(VE)

동작과정

1. 출발노드 설정
2. 최단거리 테이블 초기화
3. 다음의 과정을 n-1번 반복한다.
   1. 전체 간선 E개를 하나씩 확인한다.
   2. 각 건선을 거쳐 다른노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

• 만약 음수 간선의 순환이 발생하는지 알고 싶다면 3번과정을 한번 더 수행한다. 이때 만약 최단거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

벨만포드 VS 다익스트라

• 다익스트라
  • 매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.
  • 음수간선이 없다면 최적의 해 찾기가능
• 벨만포드
  • 매번 모든간선을 확인 (= 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다)
  • 다익스트라에 비해서는 시간이 오래걸리지만 음수 간선의 순환을 탐지할 수 있다.

 

알고리즘 코드

 

이때, 음의 간선이 존재하기 때문에 간선 (u, v)를 볼 때 먼저 dist[u]가 아직 INF인지 확인을 해야 한다.

구현에 따라서 둘 다 시작점에서 도달 불가능한 정점 u, v가 존재하고 (u, v) 가중치가 음수일 때

dist[u] = INF, dist[v] = INF-cost 꼴이 나올 수도 있기 때문!!!

 

# 노드개수, 간선개수
n,m = map(int, input().split())
# 간선정보를 담을 리스트
edges = []
# 최단거리 테이블 초기화
INF = int(1e9)
dist = [INF] * (n+1)

# 간선정보 입력받기
for _ in range(m):
    a,b,c = map(int, input().split())
    edges.append((a,b,c))

def bf(start):
    # 시작노드에 대해 초기화
    dist[start] = 0

    # 전체 n번의 라운드를 반복 (전체노드를 방문)
    for i in range(n):
        # 방문할때마다 모든간선을 확인
        for j in range(m):
            curr = edges[j][0] # 현재노드
            next_node = edges[j][1] # 목적지노드
            cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더짧은 경우
            if dist[curr] != INF and dist[next_node] > dist[curr] + cost:
                dist[next_node] = dist[curr] + cost
                if i==n-1: #n번째 라운드에서 값이 갱신되었다면 음수순환이 존재한다는것
                    return True

    return False


negative_cycle = bf(1)

if negative_cycle:
    print("음수순환이 존재한다.")
else:
    # 1번노드를 제외한 다른 모든 노드로 가는 최단거리
    for i in range(2, n+1):
        if dist[i] == INF:
            print('-1') #출발노드에서 그 지점까지 가는방법 없음
        else:
            print(dist[i])

 

참고 : 

https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

https://m.blog.naver.com/kks227/220796963742