최단 경로 (벨만-포드(Bellman-Ford))

목차

다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다.
다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우)
벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)
플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)

벨만-포드(Bellman-Ford)

• 벨만-포드 알고리즘은 간선이 음의 가중치를 가질 때, 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 
• 벨만-포드 알고리즘
  • 초기 설정 : 시작 정점의 거리 값을 0으로, 다른 모든 정점의 거리 값을 무한대로 설정합니다.
  • 업데이트 : 모든 간선에 대해 아래의 작업을 V-1번 반복합니다. (V: 정점의 수)
    • 모든 간선(u,v)에 대해, 만약 distance[u] + weight(u, v) < distance[v] 이면 distance[v]를 distance[u] + weight(u,v)로 업데이트 합니다. (이는 u를 거쳐서 v로 가는 거리가 현재 알고 있는 v까지의 거리보다 더 짧다는 것을 의미합니다.)
  • 음의 사이클 체크 : 업데이트 과정을 마지막으로 1번 더 진행해줍니다.
    • 이 과정에서 만약 업데이트 되는 정점이 존재한다면, 이는 음의 사이클이 존재하는 것입니다. (전체 정점의 수는 V개 인데, 업데이트 과정을 V번 진행한것이면 총 V+1개의 정점을 지나온 것이기 때문입니다. 음의 사이클이 없다면 최대 V-1번째에서 모든 최단 거리가 완성이 되어야합니다.)
  • 시간복잡도는 O(VE)입니다.
    • 모든 간선(E)을 V번 체크하기때문입니다.
• 음의 사이클이 없는 경우
  
  • 
    • 3->2 간선의 가중치가 -1입니다.
  • 진행 과정
    • 0번 정점부터 모든 정점에 대해 각 정점에 연결된 모든 간선을 체크하여 각 정점까지의 최단 거리를 갱신해줍니다. (즉, 모든 간선 E개를 체크하는 것입니다.)
    • 위 과정을 총 V번 진행합니다.(여기서는 6번)
    • 음의 사이클이 없을 경우 모든 간선이 모든 노드를 거쳐서 최단거리에 가는 경우라면 최대 V개의 노드를 거쳐서 갈것입니다. 따라서 최대 간선을 V-1개 지나게 됩니다.
   
  • 
    • 3->2 간선의 가중치가 -3입니다.
  • 진행 과정
    • 0번 정점부터 모든 정점에 대해 각 정점에 연결된 모든 간선을 체크하여 각 정점까지의 최단 거리를 갱신해줍니다.  (즉, 모든 간선 E개를 체크하는 것입니다.)
    • 위 과정을 총 V번 진행합니다.(여기서는 6번)
    • 이 때 위 예시에서는 음의 사이클이 존재하기때문에 V번째에서 2번 노드의 값이 업데이트 되게 됩니다.
    • 음의 사이클이 없을 경우 모든 간선이 모든 노드를 거쳐서 최단거리에 가는 경우라면 최대 V개의 노드를 거쳐서 갈것이라고 했습니다. (최대 간선 V-1개를 지날것입니다.)
    • 하지만 여기서 음의 간선이 존재하고, 그로 인해 음의 사이클이 생긴다면 음의 값으로 계속해서 갱신이 되기때문에 최단 경로로 간선을 V개 이상 지나더라도 값이 업데이트 되고 있을 것입니다. (2번 정점이 마지막까지도 최단 거리가 업데이트 되는 것을 확인할 수 있습니다.)음의 사이클이 있는 경우

예시

• 백준 11657 타임머신 문제를 살펴보겠습니다.
• 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성해야합니다. 즉 최단경로 문제입니다. 단, 여기서 가중치가 음수인 경우가 존재하므로 이는 벨만포드 알고리즘을 사용한 최단거리 문제가 된다는 것을 알 수 있습니다.
• 코드 
  

  • n,m = map(int,input().split())
    
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        s,e,c = map(int,input().split())
        graph[s].append((e,c))
    
    inf = int(1e9)
    distance = [inf for _ in range(n+1)]
    
    def bellman(start):
        distance[start] = 0
        
        for i in range(n): # i가 증가할수록 inf값이 아닌 값으로 업데이트된 노드들이 점점 많아짐. -> 그 노드들에 대해서 연결된 노드들에 업데이트 진행
            for node in range(1,n+1):
                if distance[node]!=inf:
                    for next_node,weight in graph[node]:
                        if distance[next_node]>distance[node]+weight:
                            distance[next_node]=distance[node]+weight
                            
                            if i==n-1:
                                return False
        return True
        
    
    if bellman(1):
        for i in range(2,n+1):
            if distance[i]!=inf:
                print(distance[i])
            else:
                print(-1)
    else:
        print(-1)

• 또 다른 풀이
  • 벨만포드는 어차피 모든 간선을 n번 업데이트를 진행시켜야하므로 아래처럼 코드를 작성할 수 도 있습니다.

  • import sys
    
    input = sys.stdin.readline
    INF = float('inf')
    
    # 노드의 개수 N, 간선의 개수 M
    N, M = map(int, input().split())
    
    # 간선 정보를 저장할 리스트
    edges = []
    
    # 모든 간선 정보를 입력 받음
    for _ in range(M):
        a, b, c = map(int, input().split())
        edges.append((a, b, c))
    
    def bellman_ford(start):
        # 시작 정점으로부터의 최단 거리 테이블 초기화
        distance = [INF] * (N + 1)
        distance[start] = 0
    
        # 전체 N-1번의 라운드(round)를 반복
        for i in range(1, N):
            # 매 반복마다 모든 간선을 확인
            for j in range(M):
                cur_node, next_node, cost = edges[j]
                # 현재 간선을 거쳐 다른 정점으로 이동하는 거리가 더 짧은 경우
                if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + cost:
                    distance[next_node] = distance[cur_node] + cost
    
        # 음수 사이클 체크
        for j in range(M):
            cur_node, next_node, cost = edges[j]
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + cost:
                return True, []
    
        return False, distance
    
    negative_cycle, distances = bellman_ford(1)
    
    if negative_cycle:
        print("-1")
    else:
        for i in range(2, N + 1):
            if distances[i] == INF:
                print("-1")
            else:
                print(distances[i])