벨만 포드

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

11657번: 타임머신

#특징

1. 음수 가중치가 존재하는 모든 정점에서의 최단 경로를 알 수 있음.

2. 시간복잡도 O(VE)

  정점이 V, 간선이 E라고 했을 때 V-1번 간선들을 모두 돌아봄.

3. 음의 가중치를 가지기 때문에, 음의 사이클을 조심해야함.

  ->V번째 간선들을 돌아봤을 때, 가중치가 수정이되면 음의 싸이클이 존재.

 

#다익스트라랑 vs 벨만포드

- 다익스트라

  시간 복잡도 O(V^2), 우선순위큐 사용시 O(ELogV)

  한 정점에서의 최단 경로를 가져옴.

 

- 벨만포드

  시간복잡도 O(VE)

 

-> 음의 가중치가 주어진 경우가 아니면, 우선순위큐를 이용한 다익스트라를 이용하자.

 

#소스

유의할 점은 

중복된 입력이 주어졌을때, 음의 사이클이라 생각하지 못하는 경우가 생김.

-> HashSet을 이용해 제거

https://meorimori.tistory.com/28?category=1092609 (HashSet에 클래스 중복 여부 판단)

package main.java.Temp;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class bac11657_타임머신_G4_벨만포드 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static int N;
	static int M;
	static ArrayList<Point> Arr;
	static int D[]; // 그정점까지의 최소거리

	static final int max = 1000000000;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Set<Point> Hs = new HashSet();
		D = new int[N+1];

		//배열 입력
		for(int i =0; i<M; i++){
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()) {
				int src = Integer.parseInt(st.nextToken());
				int dsc = Integer.parseInt(st.nextToken());
				int time = Integer.parseInt(st.nextToken());
				Hs.add(new Point(src,dsc,time));
			}
		}

		//중복제거후 리스트에 넣기
		Arr = new ArrayList(Hs);


		//정점 1부터 시작할것
		for(int i=2; i<=N; i++) D[i] = max;
		D[1] = 0;

		//N-1번 돌아야함, 마지막 번쨰는 음의싸이클 판단
		//그 이후로도 갱신시, 음의사이클
		for(int i=1; i<=(N-1); i++){
			for(int j=0; j<Arr.size(); j++){
				if(D[Arr.get(j).src] >= max) continue;
				if(D[Arr.get(j).dsc] > D[Arr.get(j).src] + Arr.get(j).time)
					D[Arr.get(j).dsc] = D[Arr.get(j).src] + Arr.get(j).time;
			}
		}

		boolean isCycle = false;
		for(int j=0; j<Arr.size(); j++){
			if(D[Arr.get(j).src] >= max ) continue;
			if(D[Arr.get(j).dsc] > D[Arr.get(j).src] + Arr.get(j).time)
				isCycle = true; // 더갱신됬으니.. 싸이클
		}

		//음이면
		//sb.append("");
		if (isCycle) {
			sb.append(-1);
		} else {
			for (int i = 2; i <= N; i++) {
				sb.append(D[i] == max ? -1 + "\n" : D[i] + "\n");
			}
		}

		System.out.print(sb);

	}

	public static class Point{
		int src;
		int dsc;
		int time;
		public Point(int src, int dsc, int time){
			this.src = src;
			this.dsc = dsc;
			this.time = time;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;
			Point point = (Point) o;
			return src == point.src &&
					dsc == point.dsc &&
					time == point.time;
		}

		@Override
		public int hashCode() {
			return (src+","+dsc+","+ time).hashCode();
		}
	}

}