벨만 포드, 다익스트라, 프로이드 워샬 알고리즘

벨만 포드 알고리즘

다익스트라 문제처럼 한 지점에서 다른 지점까지의 최단 경로들을 구할 때 사용하는 알고리즘

다익스트라와 차이점은 가중치에 음수가 있는 경우에는 다익스트라를 쓰면 안되므로 벨만 포드 알고리즘을 쓴다.

 

다익스트라보다 구현은 훨씬 쉽다. 단순하게 (노드수-1)번만큼 반복하는데 반복하는 일은 다음과 같다.

 방문한 노드에서 뻗어나오는 간선들을 통해서 최단경로가 갱신되는지 연산

시작하는 노드는 방문한 노드라고 처음에 설정하고 시작한다.

모든 간선을 확인할 필요는 없고 방문했던 노드와 연관된 간선들만 확인하면 되긴 하다.

 

벨만 포드 알고리즘 자체라고 생각하는 문제는 백준의 타임머신 문제이다.

11657번: 타임머신

설명보다는 보는 것이 이해가 잘된다. (코드를 보면 단순하기 때문에)

public class Main {
	static ArrayList<Edge> edge;

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		st = new StringTokenizer(bf.readLine());

		int N = Integer.parseInt(st.nextToken());// 도시수
		int M = Integer.parseInt(st.nextToken());// 버스노선
		edge = new ArrayList<Edge>();
		long[] dist = new long[N];
		for (int i = 1; i < N; i++) {
			dist[i] = Integer.MAX_VALUE;
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bf.readLine());
			int a, b, c;
			a = Integer.parseInt(st.nextToken()) - 1;
			b = Integer.parseInt(st.nextToken()) - 1;
			c = Integer.parseInt(st.nextToken());

			edge.add(new Edge(a, b, c));
		}
		
		// 시작 0번째
		boolean stop = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				Edge target = edge.get(j);
				
				if(dist[target.src]!=Integer.MAX_VALUE && dist[target.dist] > dist[target.src]+target.time) {//방문한적 있고 더 짧은 경로를 발견한 경우이다.
					dist[target.dist] = dist[target.src]+target.time;
					if(i == N-1) {//n-1번 반복하는데 n번반복함으로서 음수 순환 발견
						stop = true;
					}
				}
				
			}
		}
		
		if(stop) {
			System.out.println(-1);
		}else {
			for(int i = 1; i < N ;i++) {
				if(dist[i]!=Integer.MAX_VALUE) {
					System.out.println(dist[i]);
				}else {
					System.out.println(-1);
				}
			}
		}
		

	}

}

class Edge {
	int src;
	int dist;
	int time;

	public Edge(int src, int dist, int time) {
		this.src = src;
		this.dist = dist;
		this.time = time;
	}
}

 

번외 : 다익스트라 알고리즘 코드를 보고 순간 흠칫했다. 너무 안보면 까먹으니 틈틈히 보자.

백준: 최소비용구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<Edge>[] node_list;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int N = Integer.parseInt(bf.readLine()); // 도시
		int M = Integer.parseInt(bf.readLine()); // 노선

		int[] minEdge = new int[N];
		node_list = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			node_list[i] = new ArrayList<>();
			minEdge[i] = Integer.MAX_VALUE;
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bf.readLine());
			int s = Integer.parseInt(st.nextToken()) - 1;
			int d = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());
			node_list[s].add(new Edge(d, w));
			
		}

		st = new StringTokenizer(bf.readLine());
		int target = Integer.parseInt(st.nextToken())-1;
		int end = Integer.parseInt(st.nextToken())-1;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> {
			return e1.weight - e2.weight;
		});
		pq.add(new Edge(target, 0));
		minEdge[target] = 0;
		while (!pq.isEmpty()) {
			Edge edge = pq.poll();
//			System.out.println(edge);
//			System.out.println(node_list[edge.dest]);
			if (minEdge[edge.dest] < edge.weight) {
				continue;// 해당경로는 최단경로 이후 진행할 필요없다. 우선순위 큐라서
			}

			// 목적지까지 가는 최단 경로가 수정되었다.
			// 목적지를 타겟으로 잡고 타겟에서 뻗어나가는 간선을 확인한다.
			// 간선을 확인했을 때 다시 최단 경로를 만들 수 있는 간선이라면 큐에 넣는다.
			// dest가 같으며 가중치가 다른 요소가 큐에 동시에 존재할 수 있다.
			// 시작 지점이 다르고 dest가 같은 경우 큐에 같은 dest가 있을 수 있다.
			// 가중치가 작은 것이 우선 선택되도록 우선순위 큐 사용
			// 가중치 작은게 우선 적용 된 후 가중치가 큰 요소는 위에서 필터링되어버린다.
			for (int i = 0; i < node_list[edge.dest].size(); i++) {
				int target_dest = node_list[edge.dest].get(i).dest;
				int target_weight = node_list[edge.dest].get(i).weight;

				if (minEdge[target_dest] > edge.weight + target_weight) {
					minEdge[target_dest] = edge.weight + target_weight;
					pq.add(new Edge(target_dest, minEdge[target_dest]));
				}

			}
			//System.out.println(Arrays.toString(minEdge));
		}
//		for (int a : minEdge) {
//			if (a == Integer.MAX_VALUE) {
//				System.out.println("INF");
//			} else
//				System.out.println(a);
//		}
		
		System.out.println(minEdge[end]);

	}

	static class Edge {
		int dest;
		int weight;

		public Edge(int dest, int weight) {
			this.dest = dest;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Edge [dest=" + dest + ", weight=" + weight + "]";
		}

	}
}

플로이드 워셜 알고리즘

//dist[][]의 모든 값이 Integer.Max값으로 이루어져있다고 가정.
// a -> b (cost)일 때 인접행렬 생성했다고 가정
for (int i = 0; i < N; i++) {
	Arrays.fill(table[i], INF); 
	table[i][i] = 0;
}

dist[a][b] = Math.min(dist[a][b], cost);
dist[b][a] = Math.min(dist[b][a], cost);

for (int k = 0; k < N; k++) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}

 

플로이드 워셜은 시간복잡도가 굉장히 크기 때문에 주의해야한다.

다만 모든 정점에서 모든 정점에 대한 최단경로들을 구하고자할 때는 유리하다.