티스토리 뷰

반응형

최단경로 문제와 벨만포드 알고리즘

Shortest path Problem && Bellman-ford Algorithm (Label Correcting Algorithm)

벨만의 1958년 연구 논문의 서론 부분이다. (RAND corp.)

두 번째 문단에서, " dynamic programming의 (함수 방정식 기법) 사용과 N-1번의 반복후에 수렴하는 반복적 알고리즘이 " 를 보자.
이게 바로 벨만-포드 알고리즘의 큰 핵심이다.


Introduction


최단경로를 찾는 문제는 크게 두 종류로 나뉜다. 

1 한 점에서 임의의 한 점(다른 모든 점) 까지의 최단경로를 찾는 문제
2 모든 점 간의 최단경로를 찾는 문제

이 포스팅은 1번인 한 점에서 임의의 한 점 까지의 최단경로를 찾는 방법(알고리즘)에 대해서 포스팅 할 것이다.


한 점에서 다른 임의의 한 점 까지의 최단경로를 다음과 같이 말한다. "Single-source shortest paths" 포스팅을 하면서 용어를 섞어 사용할 수도 있다.

항상 최소한의 노력, 최소값, 또는 최대값을 탐색하라는 문제는 모든 경우의수를 다 고려해봐야 하는 문제이며,
따라서 한 점에서 임의의 점까지의 최단경로를 찾는 문제는 결코 사람의 힘으로 하기엔 쉬운 문제가 아니며, 컴퓨터의 힘을 이용해야한다. 
또한 난이도 면에서도 절대 초보용 알고리즘이 아니라고 확신한다. 

시작점을 u라고 하고 도착점을 v라고 할때 
u에서 v로 도착하는 모든 경우의수를 brute-force하게 고려하고 최소비용을 비교하면 지수시간이다.
그러나 조심스럽게 모든 경우의수를 다 고려해보면, 다항 시간내에 접근할 수 있다.  * 그렇기에 굉장한 알고리즘이다.


우리는 그렇게 조심스럽게 접근하여 완벽하게 source-single shortest path를 찾아내는 알고리즘 중 Label Correcting Algorithm, 또는 벨만 포드 알고리즘이라고 불리는 알고리즘을 살펴 볼 것 이다.


! 주의 : 이미 dynamic programming을 알고 있으면 더 쉽게 느낄 수 있다.


What Is 
Shortest Paths? (Introduction 2)


*정의 
최단경로 문제는 "방향 네트워크에서 어떤 특정 한 점에서 다른 모든 점까지의 최단 경로 (또는 최소 비용)을 찾는 것을 요구" 한다. 

그리고, 최단경로 문제는 네트워크 유량문제를 해결하는데 핵심적인 부분을 맡고있다. 
이 최단경로 문제는 연구자한테도 그리고 실용적인 사용자한테도 중요한 역할을 하는데 그 이유는 다음과 같다.

1 특정 두 점 사이간에 물건을 보내려고 할 때 가능한한 빠르고, 가능한한 싸게, 가능한한 신뢰도가 높은(고장율이 낮은) 경로로 보내려 할 때 자주 사용된다.

2 많은 조합론 문제 그리고 네트워크 최적화 문제를 풀기위한 부분 문제(subproblem)로 모습을 나타낸다.

3 그리고 이 최단경로 문제는 굉장히 효율적으로 해결될 수 있기 때문이다. 



그래프와 경로에 대한 BASIC CONCEPTS


앞으로의 Label Correcting 알고리즘을 설명하기 위해 몇 가지 용어들을 짚고 넘어가고자 한다. 이 중 몇 가지는 사실이며, 몇 개는 길게 설명할 용어를 표현의 간략함을 위해 단순히 정의하는 것에 불과하다. 최단경로에 대해 처음 나오는 용어 또는 핵심적이다고 생각되는 구문에는 굵은 글자로 강조했다.

1 그래프는 G= (V, E)로 표현할 수 있다. 여기서 V는 점들의 집합이며, E는 간선들의 집합이다. 간선은 다음과 같이 표현될 수 있다. (u, v)

1. 1 directed weighted graph는 각 E의 원소가 임의의 비용(cost)을 가지고 있다. 점 u, v 를 잇는 간선의 비용을 다음과 같이 표현하자. C_uv 


1. 2 A(u)를 점 u에서 출발하는 모든 간선들의 집합이라고 하자. A(u) = { (u, v) |  (u,v) ∈ E}


2 방향 경로 p는 다음과 같이 정의된다. p = <v0, v1, v2.. .. vk>


2.1 방향 경로 p의 비용(또는 길이)을 다음과 같이 정의된다. 

2. 2 방향 경로 p중 cycle 이 있는 경로를 Q라하자. 이때 W(Q)가 음수이면 음 가중치의 사이클이다.

- 만약 방향 간선이 사이클을 이루는데 이 간선의 가중치 합이 음수일 경우, 그 사이클을 포함한 그래프에서는 최단경로가 존재할 수없다. 만약 다음 그림에서 A에서 B로 가는 것을 생각해보자.

음수 사이클인 경우에 A에서 B로 가는 최단 경로는 항상 음수사이클을 한번 더 돌때마다 갱신된다.
그래서 경로의 비용은 음의 무한대로 발산할 수 있다. 그 땐 우리는 최단경로가 존재하지 
않는다고 표현한다.



3. 점 s로부터 e까지의 최단경로는 s에서부터 e로 가는 최소 길이(비용)의 방향 경로이다.  

3.1 방향 트리(directed out-tree)는 출발점 s로부터 뿌리를 둔 s로부터 나가는 방향의 간선을 가진 트리이다.

3.2 최단경로 트리(shortest path tree)는 출발점 s로부터 부리를 둔 out-tree 이며, 루트 s로부터 네트워크의 임의의 점 v까지의 최단경로를 포함하는 특성을 가지고 있다.

- 이 부분에서 짚고 넘어가야할 게 있다. 중요한 성질인데, 다익스트라 또는 벨만-포드 알고리즘은 결국엔 shortest path tree를 만든다. 

아래 그림은 directed out-tree의 나열을 표현했다. 그런데 이 directed out-tree 중엔 출발점으로 부터 모든 정점으로의 최단경로를 가지는 shortest path tree 가 존재하고 있다.

 우린 shortest path tree를 찾아내고 만들것이다. 이게 바로 shortest path algorithm이 하는 일이다.  그리고 이런 그래프의 간선 - 조합론 문제에서 특정한 특성을 띄는 tree를 찾는 것은 마치 - 모든 가능성이 있는 트리를 펼쳐보고는 여러분은 단지 그 중 "소중한" 트리를 찾는 문제이다. 

컴퓨터의 엄청난 계산력이 필요한 지수시간을 소요하는 문제일 것인데, 우리의 멋진 포드와 벨만아저씨는 이 문제를 다항시간Polynomial time 안에 풀 수 있는 알고리즘으로 만들었다. 그것도 1950년도에.

어때요 마법같죵? 

마법같은 알고리즘을 보기 위해 신나신 분들의 예상모습(?)



3.3 vector d( )는 거리 레이블이라고 부르며, 네트워크 임의의 점 v의 d(v)는 출발점 s로부터 v까지의 어떤 방향 경로의 길이를 나타낸다. 왜냐하면 p = <s .... v> 는 복수일 수 있기 때문이다. 이때 출발점 s의 거리 레이블은 다음을 만족한다. d(s)=0.

이 d 벡터는 최단경로 알고리즘에서 반드시 사용된다. 그러니까 다익스트라, 벨만포드, 와샬플로이드 알고리즘이 d 배열을 사용하는 것이다.

이 d 벡터를 이용해서 그래프내의 두점사이의 최단경로 중 부분 최단 경로를 기록하는데에 사용하는데, 만약 여러분이 이미 dynamic programming을 배웠더라면 d 배열이라는 존재가 더 익숙하게 느껴질 것이다.

왜 이 벨만포드 알고리즘을 label correcting algorithm으로 불렸을까? 내가 생각하기론 이 distance label vector d를 반복적으로 수정해가면서 정답을 찾아가는 것이기 때문이라고 생각한다. 그리고 최단경로 찾는 문제의 시작은 벨만- 포드 두 아저씨들이 했기에 distance label이라는 사용 자체가 그들만의 고유한 방법론이였을거라 생각한다. 물론 후에 다익스트라, 와샬-플로이드 또한 distance label을 사용했기에 label correcting algorithm보다는 bellman-ford algorithm이 더욱 정확하고 명확한 명칭이 되었을거다. 어쨌든 이 매력적인 벨만-포드만의 label correcting 방법론은 이번 포스팅에서 계속되어 설명 될 것이다.

분명하게는 vector d는 어떤 방향 경로의 길이를 나타내며 아직은 최단 방향 경로의 길이인지, 그냥 그 두 점 사이의 방향 경로의 길이인지 확실지 않은 상태이다. 물론, "최단 방향 경로"도 "그냥 두 점 사이의 방향 경로" 집합에 포함 되겠지만 전자의 경우 좀 더 특수하고 소중한 것이라서 따로 분리해서 말했다.


3.4 이 때 이 거리 레이블 d[v]가 s-v 경로의 최단 길이라면, 이 때 이 값을 최단 경로 거리라고 한다. 최단 경로 거리는 다음과 같이 표현할 수 있다.

3.4 점 s로부터 vk까지의 방향경로 p = <s, v0, v1, ... , vi, ... vk >는 전자 인덱스predecessor indices를 이용하여 표현할 수 있다. pred(v0) = s, pred(v1) = v0, ... , pred(vk) = vk-1



최단경로 알고리즘에 대한 사실들FACTS


1 최단 경로는 부분 최적 구조, 즉 부분 최단 경로가 존재한다.

다이나믹 프로그래밍에서는 전체적인 문제 해결 과정에 부분 문제의 해결 과정이 필요하게 되고, 부분 문제를 top-down 재귀메모이제이션 또는 bottom-up iterative하게 해결한다.

이런 다이나믹 프로그래밍 패러다임을 제창한것은 Richard Bellman 이고, 왠지 이 벨만-포드 알고리즘도 부분 문제 해결을 통해 전체 문제를 해결할 것 같다.

최단경로 또한 부분 문제가 있을까? 정답은 그렇다이다. 하지만 방법론에 있어선, 그래프에 따라다르다.  DAG(Directed Acyclic Graph) 인경우를 제외하고는 재귀함수를 활용한 메모이제이션 방법으론 해결할 수 없다. 이 부분에 대해서 간단하게 살펴보자면, 다음 MITOCW - dynamic programming 영상 41분쯤에서 그 반례를 알 수 있다.

https://www.youtube.com/watch?v=OQ5jsbhAv_M&t=2734s

일단은 여기까지만 도입에 대해 설명하고 어떻게 그래프가 부분 문제 구조를 가지는 지 살펴보자.


-> 만약 경로 P = <s, v0, ... vi, .., vm, ... , e>가 점 s에서 e로의 최단 경로이면, 
P의 부분 경로 Q = <s, v0, ... vi... vm>는 s에서 vm 까지의 최단 경로이다.

s에서 e까지의 최단경로 delta(s,e) 는  s로부터 e와 간선이 있는 임의의 점 v까지의 최단경로 + C_ve의 최소값과 같다. 
수식으로 표현하면 다음과 같다.

즉,s에서 e까지의 최단 경로를 찾는 여행은 s에서 임의의 점 v 까지의 최단경로 +C_ve 가 최소가 되는 것을 찾는 문제이며,
s에서 임의의 점 v 까지의 최단 경로를 찾는 여행은 s에서 임의의 점 u까지의 최단경로 + C_uv 가 최소가 되는 것을 찾는 문제이다.


-> 만약 경로 p = <s, v0, ... vi, ..., vm, .. e>가 s에서 e 까지의 최단경로라면, 
해당 경로 내 존재하는 임의의 점 vi, vj에 대하여 p_vivj = <vi, vi+1, ..., vj >는 vi에서 vj까지의 최단경로이다.


최단 경로 p가 s ~> vi ~> vj ~> vk로 분해 가능할 때, 경로 p의 비용은 다음과 같다.


만약 vi에서 vj까지 비용 W(pvivj) > W(p'vivj)를 만족하는 경로가 존재한다고하자. 그렇다면 w(p) > w(psvi) + w(p'vivj) +  w(pvjvk) 이므로 p가 최단경로라는 가정이 위배된다. 따라서, W(pvivj) > W(p'vivj)를 만족하는 경로가 존재하지 않으며, 최단경로 delta(s, e)의 부분 경로 p_(vi, vj) 또한 최단경로이다.



2 최단경로의 조건 그리고 relaxation

거리 레이블 vector d()가 최단경로임 은 그래프 내 모든 간선 (i,j)에 대하여 d(j) <= d(i) +cij 임과 동치이다.

distance label d vector는 어떤 방향 경로의 거리를 나타낸다. 여기서 d vector는 어떤 방향 경로의 거리임을 유념해라. 아직은 최단경로의 거리가 아니다! 그리고 이 알고리즘을 통해 d[v]가 출발점 s로 부터 v로 가는데에 최단 경로 비용이 된다면, 이 d[v] 비용은 s에서 v로 가는 최단 경로 비용이다.

그리고 d[ ] 벡터의 기시감은, 왠지 dynamic programming을 할때의 부분문제를 저장해놓는 공간 같기도 하다. 정답은 그렇다이다, 다만, dynamic programming 에서는 d 벡터가 한번 저장되면 절대 수정되지 않지만, 우리는 d 벡터를 꾸준하게 수정해줄 것이다. 

어디 조건에 맞추어서? 바로 위 조건인 d[j] <= d[i] + c_ij 조건에 맞도록이다. 

단지 이 조건을 만족하게끔 조심스럽게 전부의 경우를 반복적으로 조사할 것 이다. 반복적으로 조사하는 것의 아름다움은 1번에 설명했던 부분문제와 밀접한 연관이있지만 그 설명은 본격적인 벨만포드 알고리즘을 설명할 때 할것이다. 

지금까지 벨만포드 설명하고 있던것 아니였어? 
(응 아닙니다, 그래프와 최단경로 문제에 대해서 설명 했습니다.)


이 relaxation 작업은 대부분의 효율적인 최단 경로 알고리즘에 대해서 적용이 된다. 우선은 거리레이블이 d[j]<= d[i]+c_ij를 만족하게만 하도록 해보자. 다음과 같은 코드가 사용된다.


Relax(u, v)

if ( d[v] > d[u] + edge[u][v] ){

d[v] = d[u]+ edge[u][v]
pred[v] = u

}

}


이 relaxation은 dijkstra, washall-floyd 등에서도 볼 수 있다. 마치 이 수행은 기존 거리 레이블과 (갱신된 거리레이블과 간선의 비용을 더한 것)을 비교하는 것 같다. 그리고 그게 맞다.

특히 dijkstra는 single-source shortests path algorithm으로 이 벨만포드 알고리즘과 유사한 성격이 있다. 그러나 정확하게는 그래프 성격에 따라서 이 relax에서 큰 차이를 띄게되고 따라서 시간복잡도가 다익스트라가 좋다. 하지만 그 dijkstra만의 relax 성질 때문에 음 가중치의 간선이 존재할 때는 dijkstra는 정확하게 동작할 수 없다. 

dijkstra는 relaxation을 한 번하지만 Label correcting Algortihm은 |V|-1 번 수행한다. |V|-1 번 relaxation이 반복하는걸 볼 수 있을 것이다. ( 포스팅을 맨 위로 올려서 맨 처음의 Bellman 형님의 논문을 봐라, n-1번 반복한다고 하지 않았나? 그게 바로 그거다!)


3 만약 음 가중치 사이클이 있다면, 2번 조건을 만족하는 거리 레이블은 존재 할 수 없다.

- 만약 음 가중치 사이클이 있다면, 항상 d[j] 는 새로 갱신될것이다.
왜냐하면 음의 사이클이므로, j에서 출발하여 j로 도착하는 경로가 존재 할것이다. 그리고 그녀석은 항상 기존 d vector를 수정시킨다. 


4 음의 가중치 사이클이 없다면, 유일한 거리 레이블이 2번 조건을 만족하며 항상 존재한다. 그리고 최단 경로 트리 T* 가 생기게된다. (pred vector에 의해서)

- 이는 상당히 중요한 것이다. 이때 최단경로 트리 T*는 출발점으로 부터 모든 정점으로의 최단 경로 간선을 가진다는 특징이 있다. 

그러니까 모든 d vector는 그 인덱스 i가 뜻하는 i 노드 까지의 거리 레이블이 더이상 수정 될 수 없는 상태이며, i 노드에 대한 최단 경로를 가지게된다.

이게 뜻은 무엇이냐, 출발점 s 로부터 트리 내의 임의의 노드 i 까지의 최단경로를 갖게 된다는 것이다.

이는, 벨만포드와 다익스트라 알고리즘 모두 같다.

   

What Is
Bellman-ford Algorithm, Label Correcting Algorithm ?


Bellman-Ford 알고리즘은 사실 별개의 인물들 Bellman과 L.R. Ford가 다른 시간대에 연구한 이론이며 수학문제 이다. Ford의 이름은 또 다른 네트워크 문제인 그래프에서의 두 점 사이의 최대유량 Maximum Flow 문제에서 Ford-Fulkerson 알고리즘

벨만 포드 알고리즘은 간선을 이용한 비용 비교 (relaxation)를 수행하는데, 점점 목적지 v의 거리레이블 d[v]을 줄여나가며 결국 최단 경로 거리 delta( s, v)와 같아진다. 


Bellman-ford(){
    for each vertex v in V{

   d[v] = INF
    pred[v] = 0
}

for i= 1 to |V| -1 {
    for each edge(u,v) in E{

 if ( d[v] > d[u] + c_uv) {

d[v] = d[u] + c_uv

pred[v] = u

}

  }
}

for each edge(u,v ) in E{     //negative-weighted cycle detection
    if ( d[v] > d[u] + c_uv ) {

      return FALSE
    }
}

return TRUE

}


왜 |V|-1번을 해야 거 레이블 d[v] = delta (s, v) 가 되는가?


-> 임의의 점 vk가 s에서 부터 출발하여 도달할 수 있다고하자, 이때 점의 개수는 k+1 개이다.
그리고 이 경로를 p = <s, v1, v2, ... vk > 라 하고 s에서 vk까지의 최단경로이다. 최단경로는 단순 경로이므로 최대 k 간선 밖에 포함하지 않으며, 따라서, 우리가 단 i 번째의 반복 때 i 길이의 최단 경로 노드를를 획득할 때 최대 k 번 반복을 하게되면 k 길이의 최단경로를 구할 수 있다.


충분한 증명인지는 모르겠다. 하지만 어느정도의 직관을 전달 했다고는 바란다. 만약 더 궁금하다면 Introduction to algorithm 의 graph 부분을 살펴보길 권한다.


백준이 불여일견이다. 문제를 한번보자

문제보러가기 (클릭)


반응형