[그래프] 벨만포드

벨만포드

그래프에서 최단거리를 구하는 알고리즘

 

기능	특징	시간복잡도 (노드수:V, 엣지수:E)
특정 노드에서 다른 노드까지의 최단경로를 탐색한다.	음수 가중치 엣지가 있어도 수행 가능 전체 그래프에서 음수 사이클 존재 여부 판단 가능	O(VE)

 

<핵심 이론> 3단계

`그래프`, `엣지리스트`, `최단거리 리스트` 를 활용하여 최단거리를 구한다.

 

[그래프]

８　　５ ① → ② → ⑤ ↓3    ↑-4↙-2 ③ → ④ 　７

 

[엣지리스트]

edge	1	2	3	4	5	6
출발노드	null	null	null	null	null	null
종료노드	null	null	null	null	null	null
가중치	null	null	null	null	null	null

 

[정답(최단거리) 리스트]

1	2	3	4	5
null	null	null	null	null

 

Step 01)  엣지리스트로 그래프 구현, 최단경로 리스트 초기화

벨만포드 알고리즘은 엣지 중심으로 동작하기 때문에 엣지리스트로 그래프를 구현한다.

edge	1	2	3	4	5	6
출발노드	1	2	1	3	4	5
종료노드	2	5	3	4	2	4
가중치	8	5	3	7	-4	-2

 

최단경로 리스트를 생성하여 출발노드는 0, 나머지 노드는 ∞로 초기화 한다.

1	2	3	4	5
0	∞	∞	∞	∞

 

엣지리스트에 제너릭으로 적용할 Edge클래스는 일반적으로 노드변수 2개와 가중치 변수로 구성되어 있다.

(Start, End, Weight)

 

Step 02) 모든 엣지 확인 → 정답리스트 업데이트

최단거리 리스트에서 업데이트 반복 횟수는 노드갯수-1인 N(V)-1이다.

이는 노드 갯수가 N이고 음수 사이클이 없을 때 특정 두 노드의 최단거리를 구성할 수 있는 엣지의 최대갯수는 N-1이기 때문이다.

사용하는 엣지가 아무리 많아도 노드갯수-1 이상일수가 없다.

노드가 2개 있을때 엣지가 1개 이상 발생할 수 없는 기본적인 원리와

노드가 3개 로 구성되어있고 N-1즉 2개의 엣지로 연결되어있는 상태에서 1개의 엣지를 추가하게되면 사이클이 발생하기 때문이다.

(이는 MST알고리즘도 마찬가지이며, 사이클 발생시 무한대로 계속 돌기 때문에 최단거리를 구할수가 없게 된다)

 

모든 엣지 E=(S, E, W) 에서 특정 조건을 만족하면 업데이트를 실행한다.

이때 업데이트 반복 횟수가 K번 이라면 해당 시점에 정답 리스트 값은 시작점에서 K개의 엣지를 사용(연결) 했을 때 각 노드에 대한 최단거리를 뜻한다.

핵심은 *최단경로 리스트에서 시작노드 값이 무한대가 아닌 노드에 대해서만 업데이트를 진행한다*

 

업데이트 조건
· D[S] != ∞
· D[E] =  D[E] > D[S] + W  ? D[S] + W : D[E]
(조건식 : 종료노드 > 출발노드 + 가중치)
즉, 종료노드의 최단거리 리스트 값 보다 시작노드의 최단거리 리스트 값 + 가중치 가 작으면
종료노드의 최단거리 값을 새롭게 탐색한 최단거리 리스트 값으로 업데이트 한다.

 

N = 5 이므로 N-1인 4회 동안 아래와 같은 탐색과정을 진행한다.

 

Step 03) 음수 사이클 유무 확인하기.

계산과정은 마지막으로 넘기고 이론적인 설명부터 진행한다.

Step 02)를 순차적으로 진행하여 N-1회까지 진행하면 아래 계산과정과 같은 결과의 정답리스트가 완성된다.

이렇게 N-1회차까지 진행하여 정답리스트를 완성한 후 마지막으로 해당 그래프에 음수사이클이 존재하는지 확인이 필요하다
(N회차 1회 더 진행)

음수 사이클 유무를 확인하기 위해 모든 엣지를 한번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인한다.

만약 업데이트 되는 노드가 있다면, 음수사이클이 존재한다는 뜻이 된다.

이는 Step 02)에서 도출한 정답리스트가 무의미, 결과적으로 해당 그래프는 *최단거리 도출 불가 그래프* 이다.

음수사이클이 존재하면 이 사이클을 무한하게 돌 수록 가중치가 계속 감소하므로 최단거리 도출이 불가능하기 때문이다.

 

 

음수 사이클이 존재한다면 N+1, N+2 ... N+~ 회차 반복 탐색하더라도 마찬가지로 같은 위치 값이 감소한다.
또한 사이클 간선의 총 합이 음수인 것을 음수 사이클 이라고 한다!

 

---

계산 과정

1회차

노드	1	2	3	4	5
최단거리	0	∞	∞	∞	∞
K	0	0	0	0	0

1. 정답 리스트에서 ∞가 아닌 노드 1을 출발노드로 지정
2. 업데이트 조건을 비교한다.
   출발노드 ①의 종료노드는 ②와 ③ 두개 이므로 2번의 업데이트가 발생한다
   [ ① → ② ]
   종료노드 ②(∞) > 출발노드 ①(0) + 가중치(8) 
   조건이 true이므로 종료노드 ②에 최단거리 8을 저장한다.
   [ ① → ③ ]
   종료노드 ③(∞) > 출발노드 ①(0) + 가중치(3) 
   조건이 true이므로 종료노드 ③에 최단거리 3을 저장한다.

노드	1	2	3	4	5
최단거리	0	∞ 8	∞ 3	∞	∞
K	0	0 + 1	0 + 1	0	0

 

2회차

노드	1	2	3	4	5
최단거리	0	8	3	∞	∞
K	0	1	1	0	0

1. 정답 리스트에서 ∞가 아닌 노드 1, 2, 3을 출발노드로 지정
2. 업데이트 조건을 비교한다.
   출발노드 ①
   [ ① → ② ]
   종료노드 ②(8) > 출발노드 ①(0) + 가중치(8) 
   조건이 false이므로 업데이트 하지 않는다.
   [ ① → ③ ]
   종료노드 ③(3) > 출발노드 ①(0) + 가중치(3) 
   조건이 false이므로 업데이트 하지 않는다.
   출발노드 ②
   [ ② → ⑤ ]
   종료노드 ⑤(∞) > 출발노드 ②(8) + 가중치(5)
   조건이 true이므로 종료노드 ⑤에 13을 저장한다.
   출발노드 ③ 
   [ ③ → ④ ]
   종료노드 ④(∞) > 출발노드 ③(3) + 가중치(7)
   조건이 true이므로 종료노드 ④에 10을 저장한다.

노드	1	2	3	4	5
최단거리	0	8	3	∞ 10	∞ 13
K	0	1	1	0 + 1	0 + 1

 

 

3회차

노드	1	2	3	4	5
최단거리	0	8	3	10	13
K	0	1	1	1	1

1. 정답 리스트에서 ∞가 아닌 노드 1, 2, 3, 4, 5를 출발노드로 지정
2. 업데이트 조건을 비교한다.
   
   출발노드 ①
   [ ① → ② ]
   종료노드 ②(8) > 출발노드 ①(0) + 가중치(8) 
   조건이 false이므로 업데이트 하지 않는다.
   [ ① → ③ ]
   종료노드 ③(3) > 출발노드 ①(0) + 가중치(3) 
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ②
   [ ② → ⑤ ]
   종료노드 ⑤(13) > 출발노드 ②(8) + 가중치(5)
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ③ 
   [ ③ → ④ ]
   종료노드 ④(10) > 출발노드 ③(3) + 가중치(7)
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ④  
   [ ④ → ② ]
   종료노드 ②(8) > 출발노드 ④(10) + 가중치(-4)
   조건이 true이므로 종료노드 ②에 6을 저장한다.
   
   출발노드 ⑤
   [ ⑤ → ④ ]
   종료노드 ④(10) > 출발노드 ⑤(13) + 가중치(-2)
   조건이 false이므로 업데이트 하지 않는다.
   

노드	1	2	3	4	5
최단거리	0	8 6	3	10	13
K	0	1 + 1	1	1	1

4회차

노드	1	2	3	4	5
최단거리	0	6	3	10	13
K	0	2	1	1	1

1. 정답 리스트에서 ∞가 아닌 노드 1, 2, 3, 4, 5를 출발노드로 지정
2. 업데이트 조건을 비교한다.
   출발노드 ①
   [ ① → ② ]
   종료노드 ②(6) > 출발노드 ①(0) + 가중치(8) 
   조건이 false이므로 업데이트 하지 않는다.
   [ ① → ③ ]
   종료노드 ③(3) > 출발노드 ①(0) + 가중치(3) 
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ②
   [ ② → ⑤ ]
   종료노드 ⑤(13) > 출발노드 ②(6) + 가중치(5)
   조건이 true이므로 종료노드 ⑤에 11을 저장한다.
   
   출발노드 ③ 
   [ ③ → ④ ]
   종료노드 ④(10) > 출발노드 ③(3) + 가중치(7)
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ④  
   [ ④ → ② ]
   종료노드 ②(6) > 출발노드 ④(10) + 가중치(-4)
   조건이 false이므로 업데이트 하지 않는다
   
   출발노드 ⑤
   [ ⑤ → ④ ]
   종료노드 ④(10) > 출발노드 ⑤(13) + 가중치(-2)
   조건이 false이므로 업데이트 하지 않는다.

노드	1	2	3	4	5
최단거리	0	6	3	10	13 11
K	0	2	1	1	1 + 1

 

N(5)회차

노드	1	2	3	4	5
최단거리	0	6	3	10	11
K	0	2	1	1	2

 

1. 정답 리스트에서 ∞가 아닌 노드 1, 2, 3, 4, 5를 출발노드로 지정
2. 업데이트 조건을 비교한다.
   출발노드 ①
   [ ① → ② ]
   종료노드 ②(6) > 출발노드 ①(0) + 가중치(8) 
   조건이 false이므로 업데이트 하지 않는다.
   [ ① → ③ ]
   종료노드 ③(3) > 출발노드 ①(0) + 가중치(3) 
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ②
   [ ② → ⑤ ]
   종료노드 ⑤(11) > 출발노드 ②(6) + 가중치(5)
   조건이 false이므로 업데이트 하지 않는다 .
   
   출발노드 ③ 
   [ ③ → ④ ]
   종료노드 ④(10) > 출발노드 ③(3) + 가중치(7)
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ④  
   [ ④ → ② ]
   종료노드 ②(6) > 출발노드 ④(10) + 가중치(-4)
   조건이 false이므로 업데이트 하지 않는다
   
   출발노드 ⑤
   [ ⑤ → ④ ]
   종료노드 ④(10) > 출발노드 ⑤(11) + 가중치(-2)
   조건이 true이므로 종료노드 ④에 9를 저장한다.

노드	1	2	3	4	5
최단거리	0	6	3	10	11 9
K	0	2	1	1	2 + 1

 

 

+) N+1(6)회차

노드	1	2	3	4	5
최단거리	0	6	3	10	9
K	0	2	1	1	3

 

1. 정답 리스트에서 ∞가 아닌 노드 1, 2, 3, 4, 5를 출발노드로 지정
2. 업데이트 조건을 비교한다.
   출발노드 ①
   [ ① → ② ]
   종료노드 ②(6) > 출발노드 ①(0) + 가중치(8) 
   조건이 false이므로 업데이트 하지 않는다.
   [ ① → ③ ]
   종료노드 ③(3) > 출발노드 ①(0) + 가중치(3) 
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ②
   [ ② → ⑤ ]
   종료노드 ⑤(11) > 출발노드 ②(6) + 가중치(5)
   조건이 false이므로 업데이트 하지 않는다 .
   
   출발노드 ③ 
   [ ③ → ④ ]
   종료노드 ④(10) > 출발노드 ③(3) + 가중치(7)
   조건이 false이므로 업데이트 하지 않는다.
   
   출발노드 ④  
   [ ④ → ② ]
   종료노드 ②(6) > 출발노드 ④(10) + 가중치(-4)
   조건이 false이므로 업데이트 하지 않는다
   
   출발노드 ⑤
   [ ⑤ → ④ ]
   종료노드 ④(10) > 출발노드 ⑤(9) + 가중치(-2)
   조건이 true이므로 종료노드 ④에 7을 저장한다.

1	2	3	4	5
0	6	3	10	9 7

1.  

 

 

Step 03)