[Python] 음수 간선 벨만 포드 알고리즘

https://www.youtube.com/watch?v=Ppimbaxm8d8&list=LL&index=36

 

---

벨만 포드 

음의 간선이 있는 경우

음수 간선 순환이 생기는 지도 알 수 있다

시간 복잡도 O(VE)

(다익스트라는 O(ElogV))

 

벨만 포드 알고리즘

1. 출발 노드 설정

2. 최단 거리 테이블 무한으로 초기화

3. 전체 간선을 돌면서 최단 거리 테이블 갱신

3번을 노드 -1 만큼 반복

 

음수 간선 순환이 발생하는 지 확인하는 방법

3을 한 번 더 반복해서 최단 거리 테이블이 또 갱신되면 음수 간선 순환이 발생(즉 3을 노드만큼 반복하면 된다)

 

n: 노드 수

m: 간선 수

distance: 최단 거리 테이블

edges: 간선 정보

 

벨만 포드 함수

def bf(start, distance):
    distance[start] = 0
    # n번 반복(n-1, 음수 순환을 보기 위한 1번)
    for i in range(n):
        for j in range(m): # 모든 간선 돈다
            cur, next, cost = edges[j]
            if distance[cur] != INF: # 무한대면(start에서 cur 노드까지 못 가면) 패스
                if distance[next] > distance[cur] + cost: # 짧으면 갱신
                    if i == n-1: # 마지막에 갱신되면 음수 간선 순환 존재
                        return True
                    distance[next] = distance[cur]+cost
    return False

 

 

1. 음의 간선 없을 때

 

INF = int(1e9)
n = 6
m = 9
distance = [INF] * (n+1)
edges = [
    (1,2,6),
    (1,3,2),
    (2,4,2),
    (2,3,2),
    (3,5,1),
    (4,6,2),
    (5,2,1),
    (5,4,3),
    (5,6,4),
] # 출발 노드, 도착 노드, cost

 

if bf(1, distance):
    print("음수 간선 순환 O")
else:
    print(distance[1:])

[0, 4, 2, 6, 3, 7]

 

2. 음의 간선 있을 때 (순환은 없음)

 

INF = int(1e9)
n = 6
m = 9
distance = [INF] * (n+1)
edges = [
    (1,2,6),
    (1,3,2),
    (2,4,2),
    (2,3,2),
    (3,5,1),
    (4,6,2),
    (5,2,-2),
    (5,4,3),
    (5,6,4),
] # 출발 노드, 도착 노드, cost

 

 

if bf(1, distance):
    print("음수 간선 순환 O")
else:
    print(distance[1:])

 

[0, 1, 2, 3, 3, 5]

 

3. 음의 간선 있을 때 (순환 있음)

 

INF = int(1e9)
n = 6
m = 9
distance = [INF] * (n+1)
edges = [
    (1,2,6),
    (1,3,2),
    (2,4,2),
    (2,3,2),
    (3,5,1),
    (4,6,2),
    (5,2,-4),
    (5,4,3),
    (5,6,4),
] # 출발 노드, 도착 노드, cost

 

if bf(1, distance):
    print("음수 간선 순환 O")
else:
    print(distance[1:])

음수 간선 순환 O

 

 

---

시작점과 관계 없이 음수 간선 순환이 있는지 확인하고 싶을 때

distance[cur] != INF 조건을 뺀다

def bf(start, distance):
    distance[start] = 0
    # n번 반복(n-1, 음수 순환을 보기 위한 1번)
    for i in range(n):
        for j in range(m): # 모든 간선 돈다
            cur, next, cost = edges[j]
            if distance[next] > distance[cur] + cost: # 짧으면 갱신
                if i == n-1: # 마지막에 갱신되면 음수 간선 순환 존재
                    return True
                distance[next] = distance[cur]+cost
    return False