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

 

최단 경로를 구하는 알고리즘에는

1. 다익스트라 (dijkstra algorithm)
2. 벨만-포드 (Bellman-Ford algorithm)
3. 플로이드 워셜 ( 아직 공부 x )

이 존재한다.

 

다익스트라 참고 -

2022.09.23 - [ALGORITHM/알고리즘 알아보기] - [알고리즘] 다익스트라 알고리즘

 

 

다익스트라 알고리즘은 그리디(greedy)를 기반으로 우선순위 큐를 사용하여 최단 경로를 사용하는데 그리디가 기반이기 때문에 간선의 가중치가 음수 인 것이 존재하면 안 된다.

위와 같은 경로에서 A->D로 이동하는 최소 비용을 고려할 때,

다익스트라 알고리즘의 경우 근시안적 관점을 유지하기 때문에, 가중치가 감소하는 것을 고려하지 않고

B에서 D로 가는 경로를 선택하게 되기 때문이다.

 

 

벨만 - 포드 알고리즘

 

위와 같은 다익스트라 알고리즘의 한계 (가중치가 음이면 적용시키지 못함)을 극복 할 수 있는 알고리즘이다.

• 다익스트라와는 다르게 DP적 관점을 유지하게 때문에
• 즉, 모든 경우의 수를 검사하기 때문에 문제가 발생하지 않는다.
• 음수 가중치 에지가 있어도 수행할 수 있고
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
• 점화식
  
  • distance[i] = min(distance[i], distance[i] + (j에서 i까지 간선의 가중치)

 

• 모든 수를 고려하기 때문에 벨만-포드 알고리즘은 다익스트라에 비해 느릴 수 밖에 없다.
• 동작 원리 -> 간선을 최대 N-1개 사용하는 최단 경로까지 구한다.
  1. 시작 정점을 선택
  2. 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지 거리가 INF가 아니라면 거리 갱신.
  3. 최단 거리 테이블을 비용을 계산하여 갱신 -> 음의 간선이 존재한다면 갱신될 것이다.
  4. 위의 과정을 1~V-1번 반복 ( 갱신이 되지 않을 때까지)
     • 노드의 개수가 N이고, 음수 사이클이 없을 때, 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문

 

기본적인 시간 복잡도는 O(VE) 이다.

참고로, 음의 간선이 존재하는 경우 동작하지만, '음의 사이클'이 존재하는 경우에는 동작하지 않는다. (판별 가능)

 

 

 

구현

 

V : 노드의 개수

E : 간선의 개수

src : 시작 노드 1로 가정

 

주의할 점 : 음의 사이클이 존재하는지 검토 과정 필요

 

# 벨만-포드 알고리즘
n , m = map(int, input().split()) # n 노드의 수 / m 간선의 수

graph = []

for i in range(m):
    u, v, w = list(map(int, input().split()))
    graph.append([u, v, w])


def BellmanFord(src):
    # 1. 최단거리 테이블 초기화 ( 출발노드 0 / 나머지 INF )
    dist = [float("inf") for i in range(n+1)]
    dist[src] = 0

    # 2. 1~ n-1개의 노드를 사용한 최단거리 구하기 루프
    for i in range(n-1):
        for u, v, w in graph: # 입력받았던 그래프 돌기 /  u->v = w (비용)
            if dist[u] != float("inf") and dist[u]+w < dist[v]: # 1) dist[u]가 INF가 아니고, 2) dist[u] + w (지금 계산한 최단거리) 가 dist[v] (기존 최단거리) 보다 작으면
                dist[v] = dist[u]+w # 테이블 갱신

    # 3. 음의 사이클 확인
    cycle = 0
    for u, v, w in graph:
    	# 음의 사이클이 존재한다면 테이블이 갱신될 것
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            print("Graph contains negative weight cycle")
            cycle = 1
            break
    if cycle == 0:
        print('Distance from source vertex',src)
        print('Vertex \t Distance from source')
        for i in range(1, len(dist)):
            print(i,'\t',dist[i])


BellmanFord(1)

 

참고 - https://codingexplore.tistory.com/57