[Java] Bellman-ford algorithm - (그래프)간선 가중치가 음수

https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

벨만-포드 알고리즘 · ratsgo's blog

O(|V|^3)

 

다익스트라에서 나아가서

간선의 가중치가 음수여도 가능하다. 하지만 중요한 점이 있는데

* negative cycle의 존재 확인

=> 존재한다면 모든 정점까지의 거리가 음의 무한대로 간다

 

-다익스트라의 경우

출발점에서의 거리 int[] 선언

정점 연결과 거리 정보 저장

n-1번 반복 : (출발점 기준) 거리가 INF가 아닌 정점 중 가장 가까운 점 선택 -> 갱신

 

 

-벨만-포드의 경우

출발점에서의 거리 int[] 선언

정점 연결고 거리 정보 저장

n-1번 반복 :

    1번~n번 까지 모두 조회하여 최단거리 갱신

    갱신 더이상 안한다면 break

위에서 n-1번 전부 실행했다면:

    한번더 갱신

    무언가 업데이트 되었다 => 음의 사이클이 존재한다

 

package class4;

import java.util.*;
import java.io.*;

public class g3_1865{
    static List<HashMap<Integer, Integer>> table;
    static int[] dist;
    static int INF = Integer.MAX_VALUE;
    static int n, m, w;
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int tc = fs.nextInt();
        for (int tt=0;tt<tc;tt++){
            n = fs.nextInt();
            m = fs.nextInt();
            w = fs.nextInt();
            table = new ArrayList<>();
            for (int i=0;i<=n;i++) table.add(new HashMap<>());
            for (int i=0;i<m;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, wei);
                    table.get(b).put(a, wei);
                }
                else{
                    table.get(a).put(b, Math.min(wei, table.get(a).get(b)));
                    table.get(b).put(a, Math.min(wei, table.get(b).get(a)));
                }
            }
            for (int i=0;i<w;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, -wei);
                }
                else{
                    table.get(a).put(b, Math.min(-wei, table.get(a).get(b)));
                }
            }

            boolean isCycle = false;
            dist = new int[n + 1];
            for (int i=1;i<=n;i++){
                if (bellman_ford(i)){
                    isCycle = true;
                    pw.println("YES");
                    break;
                }
            }
            if (!isCycle) pw.println("NO");
        }

        pw.close();
    }

    static boolean bellman_ford(int node){
        Arrays.fill(dist, INF);
        dist[node] = 0;
        boolean update = false;
        for (int i=0;i<n-1;i++){
            update = false;
            for (int j=1;j<=n;j++){
                if (dist[j] == INF) continue;
                for (Integer k : table.get(j).keySet()){
                    if (dist[j] + table.get(j).get(k) < dist[k]){
                        dist[k] = dist[j] + table.get(j).get(k);
                        update = true;
                    }
                }
            }
            if (!update) break;
        }

        if (update){
            for (int j=1;j<=n;j++){
                if (dist[j] == INF) continue;
                for (Integer k : table.get(j).keySet()){
                    if (dist[j] + table.get(j).get(k) < dist[k]){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}