벨만-포드 알고리즘 Bellman Ford's Algorithm

벨만-포드 알고리즘

음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘.

벨만-포드 알고리즘에서 최단 경로는 출발점으로부터 도달가능하며 음의 값을 가지는 순환이 없는 경우를 의미함.

그래프에 있는 모든 정점을 한번씩 탐색함.

 

 

슈도코드

BELLMANFORD(그래프, 가중치, 시작점)

     시작점 초기화

     최단경로의 비용을 MAX으로 초기화

 

   ① 모든 경우의 수

     for ( 그래프의 모든 정점을 탐색) {

            for ( 그래프의 모든 엣지를 탐색){

               if( U를 거쳐서 V로 가는 비용 <  현재 V의 최단 비용 ){

                     V로 가는 비용 <- U를 거쳐서 V로 가는 비용

                } 

           }

      }

 

시간복잡도

O(노드갯수*엣지갯수)

 

구현 JAVA

package test;

import java.util.Arrays;

public class bellmanFord {
	
	
	public static void main(String[] args) {
		
		// [0] 시작정점, [1] 종료정점, [2] 가중치
		int[][] graph = { {0, 1,  2},
				{0, 2,  6},		
				{0, 3,  3},		
				{1, 4,  4},		
				{2, 3,  8},		
				{2, 4,  1},		
				{3, 4,  7},		
				{4, 3, -5}};
		
		// 정점별 최단경로 결과값
		int[] distance = new int[5];		
		
		//벨만-포드 실행
		bellmanFord f = new bellmanFord();
		f.bellmanFord(5, 8, graph, distance);
		
		// 정정별 최단경로 출력
		System.out.println("결과출력");
		System.out.println(Arrays.toString(distance)); 
		
	}
	
	void bellmanFord(int nodeCount, int edgeCount, int[][] graph, int[] distance) {
	
		//정점별 최단경로(비용) MAX로 초기화
		for(int i = 0; i<distance.length; i++) {
			distance[i] = Integer.MAX_VALUE;
		}
		
		//시작점 초기화
		distance[0] = 0;
		
		//모든 경우의 수 탐색 (노드 갯수 X 엣지 갯수)
		for(int n = 0; n<nodeCount; n++) {
			for(int e = 0; e<edgeCount; e++) {
				int u = graph[e][0]; //엣지 시작점
				int v = graph[e][1]; //엣지 종료점 
				int w = graph[e][2]; //엣지 가중치
				
				if(distance[v] > distance[u]+w) {
					distance[v] = distance[u]+w;
				}
			}
		}
			
	}
	
}

 

출처

• 컴퓨터 알고리즘 기초 17강 벨만-포드 알고리즘, T아카데미
• Bellman Ford's Algorithm, programiz