[Algorithm] 최단 경로 - 벨만-포드 알고리즘

* Python을 기준으로 합니다

---

최단 경로 - 벨만-포드 (Bellman-Ford) 알고리즘

- 개념

• 벨만-포드 알고리즘 : 최단 경로를 찾는 알고리즘 중 하나로, 매 단계마다 모든 간선의 가중치를 확인하여 최단 거리를 갱신하는 방식으로 동작함
  • 다익스트라와 달리 음의 가중치를 가지는 그래프에서도 동작 가능
  • 벨만-포드 알고리즘의 동작
    1. 시작 노드를 선정하고,
    2. 최단 거리 테이블을 시작 노드는 0 나머지 노드는 최대값 INF로 초기화
    3. 아래 과정을 노드 개수 -1 만큼 반복
       - 현재 노드에서 갈 수 있는 각 노드들에 대해, 전체 노드 각각을 거쳤을 때 더 짧은 최단 거리가 있는지 확인
       - 더 짧은 최단 거리가 있다면 최단 거리 테이블을 갱신
    4. 위 과정을 한번 더 수행하여 갱신되는 최단 거리가 있는지 확인
       - 있다면 그래프에 음의 순환이 있음을 의미
  • $V$개의 노드, $E$개의 간선이 있는 그래프에서 벨만-포드 알고리즘의 time complexity는 $O(VE)$

벨만-포드 알고리즘의 동작

- 구현

1. 벨만-포드 알고리즘의 구현

• 벨만-포드 알고리즘은 시작 노드로부터 모든 노드까지의 최단 경로를 찾는 방식
  - 따라서 매 반복마다 모든 간선에 대해 최단 거리를 계산하고 비교해야 함

import sys

INF = sys.maxsize #최대값

def bellman_ford(graph, start):
  N = len(graph)
  distance = [INF] * N #노드 개수 만큼 최단 거리 테이블 만듦

  distance[start] = 0 #최단거리 테이블 초기화

  for _ in range(N-1): #아래 과정을 노드개수 -1 만큼 반복
    #-----
    for cur in range(N): #현재 각 노드에서 
      for adj, cost in graph[cur]: #그래프의 다른 노드를 거쳤을 때
        if distance[cur] + cost  < distance[adj]: #최단거리가 있으면
          distance[adj] = distance[cur] + cost #최단거리 갱신

  #앞선 과정을 한번더 반복하여 음의 순환이 있는지 판별
  for cur in range(N): 
    for adj, cost in graph[cur]:
      if distance[cur] + cost < distance[adj]:
        return [-1] #음의 순환 존재
  
  return distance

• 결과 확인

#인접 리스트 형식 그래프 
graph = [
    [(1,4),(2,3),(4,-6)],
    [(3,5)],
    [(1,2)],
    [(0,7),(2,4)],
    [(2,2)]
]

#0에서 시작했을 때 최단거리
print(bellman_ford(graph, 0)) #[0, -2, -4, 3, -6]

#-------

#음의 순환 그래프 
graph = [
    [(1,5),(2,-1)],
    [(2,2)],
    [(3,-2)],
    [(0,2),(1,6)]
]

#0에서 시작했을 때 최단거리
print(bellman_ford(graph, 0)) #[-1] : 음의 순환 존재