벨만포드 알고리즘 (파이썬 구현)

벨만포드 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.

 

다익스트라 알고리즘과의 차이점

출발노드가 1번, 도착노드가 3번노드라고 하자.

다익스트라 알고리즘은 그리디 알고리즘 기반이므로 1번 노드에서 가중치가 10, 20 중 더 짧은 10을 선택해 3번으로 갈 것이고 3번 노드는 도착 노드이므로 최단거리 10을 반환할 것이다.

하지만 벨만 포드 알고리즘은 출발노드에서 갈수 있는 모든 경로를 확인하기 때문에 1->2->3 의 경로를 확인해 최단거리 5를 반환한다.

즉 벨만포드 알고리즘은 가중치에 음수가 포함되어 있는 경우 사용한다.

 

참조: https://velog.io/

동작순서

1. 출발 노드를 설정한다.

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

3. 최단거리 테이블에서 출발노드의 값을 0으로 초기화 한다.

3. 모든 간선을 확인하며 최단거리테이블을 업데이트 한다.

4. 3번 과정을 노드 수만큼 반복한다.

 

파이썬 구현

INF = (1e9)
n,m=map(int,input().split(' '))
edge=[]
for i in range(m):
    edge.append(list(map(int,input().split(' '))))

distance = [INF]*(n+1)

def bell(start):
    distance[start]=0

    for i in range(n):
        for j in range(m):
            start_node = edge[j][0]
            next_node = edge[j][1]
            weight = edge[j][2]

            #각 간선마다 도착지의 최단거리보다 출발지의 최단거리+가중치가 더 작은경우 최단거리 테이블을 업데이트한다.
            if distance[next_node]>distance[start_node]+weight:
                distance[next_node]=distance[start_node]+weight
                
                if i==n-1:
                    return True
    return False
                
correct = bell(1)

if correct:
    print(-1)
else:
    for i in range(2,n+1):
        if distance[i]==INF:
            print(-1)
        else:
            print(distance[i])