소개
벨만-포드 알고리즘은 그래프상의 한 정점에서 출발점으로 하여 다른 모든 정점에 대해서 최단 경로를 찾는 알고리즘이다. 최단 경로를 찾는 또 다른 알고리즘인 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선을 지닌 그래프에서도 동작한다. 벨만-포드 알고리즘은 그래프의 정점이
원리
정점의 개수가
시작점에서 출발해 간선을 개 이하로 거쳐 정점 로 가는 최소 경로의 길이
만약 그러한 경로가 없을 경우에는 무한대로 간주한다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
만약 정점
예시로 이해해보자. 다음과 같은 그래프에 시작점 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
0 | ∞ | ∞ | ∞ |
0 | 3 | 5 | ∞ |
0 | 2 | 5 | 4 |
0 | 2 | 5 | 3 |
이렇게 해서 완성한
음수 사이클
음수 가중치 그래프에서 최단 경로를 계산할 때의 주의할 점은 해당 그래프가 음수 사이클을 가지고 있을 수 있다는 것이다. 음수 사이클이란 어떠한 한 정점에서 다른 정점을 거쳐 다시 돌아왔을 때 비용이 더 적어지는 경로를 말한다. 다음은 음수 사이클의 한 예이다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
정점
음수 사이클의 감지는 의외로 간단하다.
구현
벨만-포드 알고리즘을 위해서는 그래프를 인접 리스트로 표현하는 것이 좋다. 왜냐하면 그래프의 간선을 기준으로 반복문을 설계할 것이기 때문이다. 먼저
INF = 1_000_000_000
# edge는 인접 리스트이다.
# edge[n]은 정점 n에서 뻗어나온 모든 간선의 정보를 담은 리스트이다.
# 각 간선은 (다음 정점 번호, 간선의 가중치)의 형태로 표현한다.
def bellman_ford(edge: list[list[tuple[int, int]]], start_node: int) -> list[int]:
result = [INF] * len(edge)
result[start_node] = 0
for step in range(len(edge)):
for node in range(len(edge)):
for next_node, cost in edge[node]:
if result[next_node] > result[node] + cost:
result[next_node] = result[node] + cost
# 음수 사이클 판정
if step == len(edge) - 1:
raise Exception("음수 사이클 감지됨")
return result
정점이