벨만 포드 알고리즘

• 간선 중심 알고리즘 👉 그래프들을 에지 리스트로 구현
• 음수 간선이 포함된 상황에서의 최단 거리 문제에 사용.
• 음수 간선의 순환을 감지할 수 있음.
• 매번 모든 간선을 전부 확인
• 최단 거리 리스트에서 업데이트 반복 횟수는 V - 1
• 시간복잡도 :  O(VE), 다익스트 알고리즘에 비해 느리다

음수간선이 있어도 순환이 발생하지 않는다면 최단거리를 계산할 수 있다.
(음수간선의 순환이 발생하면 최단거리가 음의 무한인 노드가 발생하게 됨)

 

동작원리

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

3. 다음의 과정을 N-1 번 반복

     3-1. 전체 간선 E개를 하나씩 확인

     3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신

4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행.

     4-1. 만약 최단거리 테이블이 갱신된다면 음수 간선 순환이 존재한다는 뜻이다.

 

• 다익스트라 
  • 매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택
  • 음수 간선이 없다면 최단거리를 찾을 수 있다.
• 벨만 포드 알고리즘
  • 매번 모든 간선을 전부 확인 (다익스트라 알고리즘보다 느리다)
  • 음수 간선 순환을 탐지할 수 있음.

코드

import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start):
	# 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드(round)를 반복
    for i in range(n):
    	chk = False
    	# 매 반복마다 "모든 간선"을 확인
        for j in range(m):
        	cur = edges[j][0]
            next_node = edge[j][1]
            cost = edge[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
            	chk = True
            	dist[next_node] = dist[cur] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i==n-1:
                	return True
         if (not chk): # chk가 False이면 더 이상 간선이 업데이트될 게 없기 때문에, 더 반복문을 돌릴 필요가 없다.
         	break
            
     return False
 
 n,m = map(int,input().split())
 edges = []
 dist [INF] * (n+1)
 
 for _ in range(m):
 	a,b,c = map(int,input().split())
    edges.append((a,b,c))
    
negative_cycle = bf(1) # 벨마포드 수행, 1번노드가 시작노드

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

 

 

---

음수순환 검사하는  벨만포드 알고리즘 (백준 1865번)

https://www.acmicpc.net/problem/1865

• dist[cur] != INF 조건을 제거
• 이때 임의의 점을 출발점으로 잡아도 된다.
• 최단경로는 구하지 못함

package com.mincheolsong;
import java.io.*;
import java.util.*;

class Node{
    int from, to, w;

    public Node(int from, int to, int w){
        this.from = from;
        this.to = to;
        this.w = w;
    }

}

public class Main {

    // 벨만포드
    static final int INF = (int)1e9;
    static int N,M,W;
    static List<Node> graph;
    static int[] dist;

    static boolean solve(){
        Arrays.fill(dist,INF);
        dist[1]=0; // 시작정점은 1로 (아무거나) 초기화

        for(int i=1;i<=N;i++){

            boolean chk = false;

            for(int j=0;j<graph.size();j++){ // 모든 간선
                Node node = graph.get(j);

                if(dist[node.to] > dist[node.from] + node.w){
                    dist[node.to] = dist[node.from] + node.w;
                    chk = true;

                    if(i==N){ // N번째에도 갱신이 일어나면 음수 순환이 있음
                        return true;
                    }
                }
            }
            if(!chk){ // chk가 false이면 더 이상 간선이 업데이트될 게 없기 때문에, 더 반복문을 돌릴 필요가 없다.
                break;
            }

        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int TC = Integer.parseInt(br.readLine());

        for(int t=0;t<TC;t++){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());

            graph = new ArrayList<>();
            dist = new int[N+1];


            for(int m=0;m<M;m++){
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
                graph.add(new Node(from,to,weight));
                graph.add(new Node(to,from,weight));
            }

            for(int w=0;w<W;w++){
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
                graph.add(new Node(from,to,-weight));
            }

            boolean ans = solve();
            if(ans){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }

        }


    }


}