[알고리즘] 그래프 알고리즘 1. 벨만-포드 알고리즘

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

• 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 사용.
• 다익스트라 알고리즘과 다르게 음의 가중치를 갖는 간선이 있어도 사용 가능하다.
• 다익스트라 알고리즘은 매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택해 나가는 반면(Greedy한 방식) 벨만-포드 알고리즘은 매 단계마다 모든 간선을 전부 확인하기 때문에 시간복잡도가 더 높다.
• 단, 음의 사이클이 존재하지 않아야 한다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 길어봐야 V-1개의 간선을 지난다는 가정이 적용된다.

알고리즘 개요

• 동적 계획법, relaxation 기법을 사용한다.
• O(nm)의 시간복잡도를 가진다.

1. dist(출발 노드와 거리) 테이블을 초기화 한다. (INF로 초기화)
2. 정점의 갯수 N만큼 아래를 반복한다.
   2-1) 간선 M개를 모두 살펴본다. 간선(a->b)의 dist[b]값이 무한대가 아니라면 2-2)를 진행한다.
   2-2) dist[cur] = min(dist[cur], dist[a] + cost(a,b))
3. 2의 과정을 한번 더 반복했을 때 dist 테이블이 갱신된다면 음의 사이클이 존재한다.

소스 코드

public void BellmanFord(int n, int m ,int start) {
	int[] dist = new int[n + 1];
    Arrays.fill(dist, INF);
    dist[start] = 0;
    
    //2.정점의 갯수 만큼 relaxation 진행 
    for (int i = 0; i < n; i++) {
    	//2-1.간선의 개수만큼 살펴봄
        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;
				}
        }
    }	
    
    //3.음수 사이클 확인
    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;
			}
    }
}