최단거리 찾기 2 - 벨만-포드(bellman-ford-moore) 파이썬, 백준 11657 파이썬

1. 벨만-포드 알고리즘

개요

그래프에서 최단 거리를 구하는 알고리즘.

다익스트라 알고리즘과 달리 에지의 가중치가 음수여도 사용할 수 있으며, 이로 인해 음수 사이클 존재 여부 확인 문제에서 많이 사용

 

다익스트라 알고리즘의 시간복잡도(O(ElogV))에 비해 표에 보이는 것과 같이 노드가 그대로 곱해지므로 음수 가중치 에지가 있거나 음수 사이클의 존재 여부를 판단할 때 사용하는 것이 좋음.

 

구현 방법

특징: 그래프를 에지 번호에 따라 출발 노드, 종료 노드, 가중치로 이루어진 에지 리스트로 구현함.

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화
   1. 최단 경로 리스트의 경우 출발 노드를 0, 나머지 노드를 무한대로 초기화
2. 정답 리스트 업데이트하기
   1. 모든 에지를 확인해 sp[src_node]가 무한이 아니며(출발 노드를 방문 했을 경우) sp[dest_node] > sp[src_node] + w 일 때(dest_node에 도달하는 새로운 값이 최소값일 경우) sp[dest_node] = sp[src_node] + w 로 최단 거리 리스트의 값을 업데이트
   2. 1을 K번(V-1) 반복
      1. 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은
         시작점에서 K개의 에지를 사용했을 때, 각 노드에 대한 최단 거리
         (모든 에지를 확인하는 경우 )
      2. 업데이트 반복 횟수: V - 1
         1. 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 V - 1이기 때문
3. 음수 사이클 유무 확인하기
   1. 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인
      1. 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻 → 최단 거리 도출 불가

쓰이는 곳

• 음수 사이클 판별 문제

 

 

백준 11657

import sys
input = sys.stdin.readline
print = sys.stdout.write

INF = 10**8
N, M = map(int, input().split())
sp_list = [INF for i in range(N+1)]
e_list = [[] for i in range(M+1)]

# 에지 리스트 초기화
for i in range(1, M+1):
    e_list[i] = list(map(int, input().split()))

# sp_list 초기값 설정
sp_list[1] = 0

def bellman_ford():
    for j in range(1, N):
        for i in range(1, M+1):
            # 출발 노드가 방문한 적이 없는 노드일 때 값을 업데이트하지 않음
            s, d, w = e_list[i]
            if sp_list[s] != INF:
                if sp_list[d] > sp_list[s] + w:
                    sp_list[d] = sp_list[s] + w
    for i in range(1, M + 1):
        # 출발 노드가 방문한 적이 없는 노드일 때 값을 업데이트하지 않음
        s, d, w = e_list[i]
        if sp_list[s] != INF:
            if sp_list[d] > sp_list[s] + w:
                break
    else: # 끝까지 다 마쳐서 음수 사이클 존재하지 않으면
        return True
    return False

is_possible = bellman_ford()
if is_possible:
    for i in range(2, N+1):
        if sp_list[i] == INF:
            print('-1\n')
        else:
            print(str(sp_list[i]) + '\n')

else:
    print('-1')