https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
벨만-포드 알고리즘 · ratsgo's blog
이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 벨만-포드 알고리즘(Bellman-Ford’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학
ratsgo.github.io
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());
}
}
}
'PS > Algorithms' 카테고리의 다른 글
[Java] Knapsack Problem - 배낭 문제(DP) (0) | 2022.01.19 |
---|---|
[Java] LIS - 최장 증가 부분 수열 (0) | 2022.01.18 |
[Java] LCS - 최장 공통 부분 수열 (0) | 2022.01.18 |
[Java] Floyd-Warshall algorithm - (그래프)모든 정점 간의 최단거리 (0) | 2022.01.08 |
[Java] Dijkstra algorithm - (그래프)간선 가중치가 양수 (0) | 2022.01.08 |