벨만포드 알고리즘

벨만포드 알고리즘

다익스트라 알고리즘과 동일하게 최단거리를 구하는 알고리즘

차이점은 간선이 단방향 음의 가중치를 가지고 있음

 

Step 1. 시작 정점부터 다른 정점까지의 거리 값을 무한으로 초기화합니다. (시작 정점은 0)

Step 2. 현재 정점의 모든 인접 정점들을 탐색하여 인접 정점까지의 거리보다

            현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신 

Step 3. 만약 정점의 개수이상으로 진행이 되고 가중치가 갱신이 되면 음의 사이클 존재

 

// true: 음수 순환 존재, false: 음수 순환 존재하지 않음

static boolean bellmanford(int start){
		
		dist[start] = 0;
		
		// 정점의 개수인 n번 반복 
		for(int i=0; i<n; i++) {
			// 매 반복마다 모든 간선을 확인 
			for(int j=0; j<m; j++) {
				int cur = e[j].u;
				int next = e[j].v;
				int cost = e[j].val;
						
				if(dist[e[j].u] == INF) 
					continue;
				// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 
				if(dist[next] > (dist[cur] + cost)) {
					dist[next] = dist[cur] + cost;
							
					// 값이 갱신되고 n번째 라운드라면 음수 순환 존재 
					if (i == n-1) {
						return true;   
					}
				}
			}
		}
		return false;
	}

 

예제코드 : https://sorjfkrh5078.tistory.com/30

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