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

1. 벨만포드 알고리즘

음수 간선이 포함되어있는 상황에서 최단거리 혹은 최소비용을 도출하고자 할때 사용할 수 있다(*다익스트라, 플로이드 와샬은 모두 간선이 양수).

2. 음의 간선이 존재할 경우의 모순

다익스트라를 통해 음수간선이 포함되어있는 상황에서 최단거리를 도출해낼 수는 있다. 단, 최단경로가 음의간선을 고려하였어도 양의 정수가 나올 경우에 해당한다.

위처럼 음의간선을 고려하였을때 최단 경로가 음수가 나올 경우 모순에 해당되어, 끝없이 음의 방향으로 최소값을 도출하는 무한반복에 빠지게 된다.

따라서 위의 경우에는 다익스트라를 통해 최소값을 구할 수 없다.

3. 음의 간선이 있는 경우 graph를 해결할 수 있는 방안

• 모든 간선이 양수일 경우 → 다익스트라
• 음수 간선이 존재할 경우
  음수순환이 있을때 → 벨만포드
  음수순환이 없을때 → 벨만포드

※ 벨만포드 알고리즘은 음수순환이 발생하는지 감지할 수 있고, 기본적으로 다익스트라 알고리즘에 비해 느리다(O(VE)).

3. 벨만포드 알고리즘의 과정과 다익스트라와의 비교

• step 1. 출발노드를 설정한다.
• step 2. 최단거리 테이블을 초기화한다(INF * (n+1))
• step 3. 전체 간선 E개에 대해 경로를 하나씩 모두 확인하며, 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블에 반영한다.
• step 3번을 반복하며, 3번을 더 수행하였을때 최단거리가 갱신된다면 음의 순환이 존재하는 것으로 판단할 수 있다.

※ 다익스트라 알고리즘

• 매번 방문하지 않은 노드에서 최단거리가 가장 짧은 노드를 선택하여 해당 노드를 거쳐가는 노드로 조사한다.
• 매단계마다 최적의 해가 도출된다는 가정으로, 다음 단계의 처리를 진행한다.
• 인접노드 및 간선에 대한 경로를 탐색해가면서 최단거리 테이블을 갱신한다.

※ 벨만포드 알고리즘

• 매번 모든 노드와 간선을 확인하고, 이때 다익스트라의 최적의 해를 포함한다.
  ※ 어차피 매 모든 간선을 확인해야 하고, heap 구조를 활용할 필요없이 그냥 edge정보에 저장한다.
• 음수순환탐지가 가능하고, 다익스트라에 비해 시간이 더 오래 걸린다.

4. 알고리즘 구현

N개의 도시가 있다.

• 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M대가 있다.
• 각 버스는 A, B, C로 나타내며 A는 시작도시, B는 도착도시, C는 소요시간이다.
• 단, C가 양수가 아닌 경우가 있는데, C=0일때는 순간이동, C<0일때는 타임머신으로 되돌아가는 경우다.

1번도시에서 출발하여 나머지 도시로 가는, 가장 빠른 시간을 구하는 알고리즘은?

#음수간선이 포함되어있는 상황에서의 최단거리
#벨만포드 알고리즘

##일단 음수간선인 경우가 있기 때문에 벨만포드 알고리즘.
##참고) 특정 도시에서 모든 도시로의 최단 경로이므로, 간선이 양수라면 다익스트라 사용
## 1<= N <= 500, 1<= M <=6000

import sys
INF = int(1e9)
#노드개수, 간선개수
n, m = map(int ,sys.stdin.readline().split())
#모든 간선에 대한 정보를 담는 리스트
edges = []
#최단 거리 테이블을 일단은 모두 무한으로 초기화
dist = [INF] * (n+1)

#모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    #a에서 b로가는 비용이 c
    edges.append((a,b,c))

#벨만 포드 알고리즘
def bf(start):
    #최초 거쳐가는 노드는 자기자신, 거리는 0
    dist[start] = 0
    #모든 노드와 간선에 대해 반복
    for i in range(n):
        for j in range(m):
            #어차피 모든 간선을 확인해야하므로
            current_node = edges[j][0]
            next_node = edges[j][1]
            cost = [j][2]
            #현재 간선을 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[current_node] != INF and dist[next_node] > dist[current_node] + cost:
                dist[next_node] = dist[current_node] + cost
                # n번째 순환에서도 값이 갱신된다면 음수 순환이 존재하는 것으로 간주
                if i == n-1:
                    return True #음수순환이 존재
    return False

#알고리즘 수행
negative_cycle = bf(1) #출발노드는 1

if negative_cycle:
    print(-1)
else:
    for i in range(2, n+1): #1번노드를 제외하고, 다른 모든 노드로 가기위한 최단거리 출력
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i], end=' ')

5. 참조자료

이코테 2021 - 벨만포드
https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13