[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 구현 - 파이썬(Python)

벨만-포드 알고리즘 (Bellman-Ford Algorithm) 구현 - 파이썬(Python)

 

 

↓벨만 포드 알고리즘 에 대한 개념은 이전 게시글에 정리해두었다.

codingexplore.tistory.com/57

[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

 

이번에는 파이썬 (Python) 으로 어떻게 벨만 포드 알고리즘을 구현할 것인가에 대한 것이다.

 

 

구현 - O(VE) : V 노드의 개수 E 간선의 개수

시작 노드(src) 가 1일 경우를 가정

구현 시 주의해야 할 점은 벨만 포드 알고리즘은 '음의 사이클' 일 경우 정상적으로 동작하지 않기 때문에

반드시 음의 사이클을 검토하는 과정이 필요하다는 점이다.

# 벨만-포드 알고리즘
n , m = map(int, input().split()) # n 노드의 수 / m 간선의 수

graph = []

for i in range(m):
    u, v, w = list(map(int, input().split()))
    graph.append([u, v, w])


def BellmanFord(src):
    # 1. 최단거리 테이블 초기화 ( 출발노드 0 / 나머지 INF )
    dist = [float("inf") for i in range(n+1)]
    dist[src] = 0

    # 2. 1~ n-1개의 노드를 사용한 최단거리 구하기 루프
    for i in range(n-1):
        for u, v, w in graph: # 입력받았던 그래프 돌기 /  u->v = w (비용)
            if dist[u] != float("inf") and dist[u]+w < dist[v]: # 1) dist[u]가 INF가 아니고, 2) dist[u] + w (지금 계산한 최단거리) 가 dist[v] (기존 최단거리) 보다 작으면
                dist[v] = dist[u]+w # 테이블 갱신

    # 3. 음의 사이클 확인
    cycle = 0
    for u, v, w in graph:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            print("Graph contains negative weight cycle")
            cycle = 1
            break
    if cycle == 0:
        print('Distance from source vertex',src)
        print('Vertex \t Distance from source')
        for i in range(1, len(dist)):
            print(i,'\t',dist[i])


BellmanFord(1)

 

입력 예시	출력 예시
3 4 1 2 4 1 3 3 2 3 -1 3 1 -2	Distance from source vertex 1 Vertex   Distance from source 1        0 2        4 3        3

 

 

---

참고자료

gist.github.com/ngenator/6178728

Bellman-Ford algorithm in python

cppsecrets.com/users/5629115104105118971091101011031055657495564103109971051084699111109/Python-Bellman-Ford-Algorithm.php

Python Bellman Ford Algorithm | Python | cppsecrets.com