99클럽 코테 스터디2 - 1일차(벨만포드)

문제 : https://www.acmicpc.net/problem/11657

🚨 오늘의 학습

⭐️ Bellman-Ford(벨만 포드)

가중치 그래프에서 음의 가중치를 포함해 최단경로를 구하는 알고리즘
음수 사이클의 존재 확인

(1) 금융 시스템
- 환율을 그래프로 나타낸 뒤, 음의 사이클이 있으면 무한히 이득을 볼 수 있는 차익 거래가 가능, 이를 판별하여 시스템의 부정행위를 방지할 수 있습니다

(2)교통 경로 설계

• 경로 비용이 음수로 설정된 경우, 잘못된 계산이 발생할 수 있습니다.
  음의 사이클을 감지하고 제거하여 경로를 정상적으로 설계할 수 있습니다.

※ 음의 사이클

• 사이클(닫힌 경로) 상에 존재하는 간선들의 가중치 합이 음수인 경우
• N개의 노드가 있는 그래프에서 최단 경로를 계산한 뒤, 추가로 한 번 더 Relaxation이 발생하면 음의 사이클 존재

🗝️ 간선 중심 그래프는 간선 리스트로 구현

🗝️ 가중치에 따른 자료형 주의 ⛔️ 누적연산 고려 ✅

🔅벨만 포드 vs 다익스트라🔅

벨만 포드	다익스트라
모든 간선의 최단거리 탐색	방문하지 않은 노드 중에서 최단거리 탐색
간선 중심	연결 노드 중심
간선리스트	연결리스트

---

package com.example.algorithm.bellmanFord;

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

public class BJN_11657 {
    /**
     * 음의 가중치를 포함한 각 노드의 최단거리 구하기
     *
     * */

    static int N; // 도시 개수 == 엣지
    static int M; // 노선 수 == 노드

    static Edge[] eg;

    public static class Edge {
        int start;
        int end;
        long hour;

        public Edge(int start, int end, long hour) {
            this.start = start;
            this.end = end;
            this.hour = hour;
        }
    }

    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        long[] dist = new long [N+1];

        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[1] = 0;


        eg = new Edge[M];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            long time = Integer.parseInt(st.nextToken());
            eg[i] = new Edge(from, to, time);
        }

        boolean isCycle = bellmanford(dist);

        if (isCycle) {
            System.out.println(-1);
        } else {
            for (int i = 2; i < dist.length; i++) {
                if(dist[i] == Integer.MAX_VALUE) {
                    System.out.println(-1);
                } else {
                    System.out.println(dist[i]);
                }
            }
        }



    }

    public static boolean bellmanford(long[] dist) throws Exception{
        boolean isMinusCycle = false;


        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < M; j++) {
                Edge cur = eg[j];
                if (dist[cur.start] == Integer.MAX_VALUE) {
                    continue;
                }

                if (dist[cur.end] > dist[cur.start] + cur.hour) {
                    dist[cur.end] = dist[cur.start] + cur.hour;
                    if (i == N) {
                        isMinusCycle = true;
                        break;
                    }
                }
            }
        }


        return isMinusCycle;
    }

}