벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘은 그래프에서 단일 출발지 최단 경로 를 찾는 알고리즘으로, 음(-)의 가중치 간선 이 있는 경우에도 사용할 수 있는 것이 특징입니다.

알고리즘 설명

1. 초기화: 출발 정점의 거리는 0으로 설정하고 나머지 정점의 거리는 ∞(무한)으로 설정합니다.
2. 반복(정점 개수 - 1번): 모든 간선을 하나씩 검사하면서, 더 짧은 경로가 발견되면 갱신합니다.
3. 음수 사이클 검사: 마지막 반복 이후에도 경로가 갱신되면 음수 사이클이 존재하는 것으로 판단합니다.

---

수식

• 주어진 간선 와 가중치 에서, 만약 [ ] 이면 를 로 갱신합니다.

---

시간 복잡도

• 
  정점의 개수 와 간선의 개수 에 비례합니다.

---

장단점

• 장점: 다익스트라 알고리즘과 달리 음의 가중치 간선 을 처리할 수 있음.
• 단점: 음수 가중치 사이클 이 존재할 경우 최단 경로를 찾을 수 없음.

---

예제

다음 그림과 같은 정점과 간선이 있다.

• 정점 위의 숫자는 정점의 번호이다.
• 간선 위의 숫자는 간선의 가중치를 의미한다. 가중치는 음수(minus)도 가능하다.

python

def bellman_ford(graph, V, src):
    # 거리 초기화
    dist = [float("inf")] * V
    dist[src] = 0
    
    # 모든 간선에 대해 V-1번 반복
    for _ in range(V - 1):
        for u, v, w in graph:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 음수 사이클 확인
    for u, v, w in graph:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            print("음수 사이클이 존재합니다.")
            return

    # 결과 출력
    for i in range(V):
        print(f"정점 {i}로의 최단 거리: {dist[i]}")

# 예제 입력 (정점 5개, 간선 리스트)
graph = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]

bellman_ford(graph, 5, 0)

• 이 코드는 출발지(정점 0)에서 각 정점으로의 최단 거리를 출력합니다.

정점 0로의 최단 거리: 0
정점 1로의 최단 거리: -1
정점 2로의 최단 거리: 2
정점 3로의 최단 거리: -2
정점 4로의 최단 거리: 1

view raw Bellman-Ford Algorithm.ko.md hosted with ❤ by GitHub