[알고리즘]그래프6 - 벨만포드(feat. Java)

벨만-포드(Bellman-Ford) 알고리즘

• 그래프 최단 경로를 구하기 위한 알고리즘
• 하나의 정점에서 출발하는 최단 거리를 구함
• 음수 싸이클 없어야 함, 음수 가중치는 허용
• O(mn) 시간 복잡도

 

 

과정

• dist : 출발지로부터 최단 거리를 기록하는 1차원 배열. 출발지는 0 / 나머지는 무한으로 초기화
• 정점의 개수 n만큼 아래를 반복
• 간선 m개를 하나씩 살펴본다. 현재 간선의 가중치를 cost(v, w)라고 하면 dist[v]는 지금까지 계산한 출발지에서 v까지 최소 거리이다. dist[v]가 무한대가 아니라면 아랫단계 진행
• 지금까지 계산한 dist[v]와 dist[v]+cost(w, v) 중 최솟값을 다시 dist[v]에 할당

 

• n = 5, m = 9, 출발 정점은 4

 

• dist 배열에 무한이 아닌 값은 4이므로 v = 4 정점만 다룸
• 인접한 정점은 1, 5번 노드
• dist[1]은 기존의 값이 무한과 dist[4] + cost(4.1)인 0 + 8 중 작은 값인 8로 갱신
• dist[5]은 기존의 값이 무한과 dist[4] + cost(4.5)인 0 + 3 중 작은 값인 3으로 갱신

 

• dist 배열에 무한이 아닌 값은 1, 4, 5이므로 v = 1, 4, 5 정점만 다룸
• dist[4] = 0
• dist[1] = 8
  • dist[2]은 기존의 값이 무한과 dist[1] + cost(1.2)인 8 + 10 중 작은 값인 18로 갱신
  • dist[3]은 기존의 값이 무한과 dist[1] + cost(1.3)인 8 + 5 중 작은 값인 13으로 갱신
• dist[5] = 3
  • dist[2]은 기존의 값이 18과 dist[5] + cost(5.2)인 3 + 31 중 작은 값이 18로 변경되지 않으므로 갱신X

 

• dist 배열에 무한인 값이 없으므로 모든 간선을 위의 방식대로 n번까지 반복한다.

최종적으로는, 위의 dist 배열의 값들로 배열이 초기화됨

 

 

 

코드 구현

class Edge {
	int v; // 나가는 정점
	int w; // 들어오는 정점
	int cost;

	public Edge(int v, int w, int cost) {
		this.v = v;
		this.w = w;
		this.cost = cost;
	}
}

public class Main {
	static ArrayList<Edge> graph;
	static final int INF = 1000000000;
	
	//정점의 개수, 간선의 개수, 출발지
	public static boolean BellmanFord(int n, int m, int start) {
		int[] dist = new int[n + 1];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		//정점의 개수만큼 반복
		for (int i = 0; i < n; i++) {
			//간선의 개수만큼 반복
			for (int j = 0; j < m; j++) {
				Edge edge = graph.get(j); //현재 간선
				
				//현재 간선의 들어오는 정점에 대해 비교
				if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
					dist[edge.w] = dist[edge.v] + edge.cost;
				}
			}
		}
		
		//음수 가중치 확인
		for (int i = 0; i < m; i++) {
			Edge edge = graph.get(i); //현재 간선
			
			//현재 간선의 들어오는 정점에 대해 비교 -> 더 작은 값 생기면 음수 사이클 존재
			if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
				System.out.println("음수 사이클 존재");
				return false;
			}
		}
		
		//출력
		for (int i = 1; i < dist.length; i++) {
			if (dist[i] == INF)
				System.out.print("INF ");
			else
				System.out.print(dist[i] + " ");
		}
		
		return true;
	}

	public static void main(String[] args) throws IOException {
    
    //그래프 입력받기
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		// 정점의 개수, 간선의 개수 
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		graph = new ArrayList<>();

		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());

			graph.add(new Edge(v, w, cost));
		}
		
        //벨만-포드 알고리즘 수행
		BellmanFord(n, m, 4);
	}
}