벨만-포드 ✔

이론 ✌

다익스트라 알고리즘은 음의 간선이 포함되지 않은 상황에서의 최단경로를 찾는 알고리즘인데, 그러면 음의 간선이 포함된 상황에서의 최단 거리 문제는 ??

1️⃣ 단순히 음의 간선만 그래프에서 포함이 되는 경우

그래프에서 음의 간선이 포함되어도 최단 경로를 찾는데에는 ❗ 문제가 없음 ❗예를 들어 노드 1에서 노드2로 가는 최단 경로는 1->3->5->2 인 비용이 1이다.

2️⃣ 음의 간선 + 음수 간선의 순환이 포함되는 경우

다익스트라는 매 번 가장 짧은 비용의 노드(a)를 선택해서 인접노드(b,c,d)들 중에서 만약 a를 거쳐서 b,c,d로 가는 비용이 이전에 시작 노드에서 b,c,d로의 최단 경로 비용을 기록한 거리 테이블의 내용보다 더 작으면 기록을 갱신하는데, cycle이 발생하는 곳에 음수 간선이 포함되어 있다면 반복적으로 갱신하는 성질상 매번 음수를 더하게 된다면 계속해서 작아질 테니깐 최단 경로 비용이 음의 무한인 노드가 발생할 것임

벨만-포드 최단 경로 알고리즘 🏆

• 음의 간선이 포함된 상황에서도 사용가능
• 음수 간선의 순환 감지
• 벨만 포드의 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느림

벨만-포드 동장과정 🔽

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음 과정을 N-1번 반복
   • 모든 간선 E개를 하나씩 확인
   • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
4. 음수 간선 순환이 발생하는지 체크할려면 3번의 과정을 한 번 더 수행
   • 이때 최단 거리 테이블이 갱신이 된다면 음수 간선 순환이 존재하는 경우 음의 사이클이 존재한다고 판단

나조차 글로만 보기에는 이해가 어려워서 참조 링크를 남김

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

def bf(start):
  # 시작 노드에 대해서 초기화
  dist[start] = 0
  # 전체 n번의 라운드(round)를 반복
  for i in range(n):
    # 매 반복마다 "모든 간선"을 확인
    for j in range(m):
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]
      # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
      if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
        dist[next_node] = dist[cur] + cost
        # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
        if i == n - 1:
          retrun True

  return False

# 노드이 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
dist = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
  a, b, c = map(int, input().split())
  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
  edges.append((a, b, c))

negative_cycle = bf(1) # 1번 노드가 시작 노드

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