Im4u 봄방학캠프 DAY 6; Elementary Graph Theory (II) 구종만 jongman@gmail.com
오늘할이야기 최단거리 (Shortest Path) 교과서알고리즘 : Dijkstra s, Floyd s, Bellman- Ford s 그래프모델링 (modeling) 문제에서어떻게그래프를뽑아낼것인가? 최단거리의변형 : multiplicative, etc.
최단거리문제 그래프위에서두점을잇는경로중가중치합의최소값을구한다 실제경로를구하는것이아니다
최단거리문제 그래프의형태 / 원하는값에따라다양한알고리즘들이존재 Single-Source 하나의시작점으로부터다른모든정점까지의거리 All-Pairs 모든 ( 시작점, 끝점 ) 까지의거리
음수가중치를갖는간선의중요성 음수간선이있는그래프에서동작하지않는최단거리알고리즘도있음 가중치의합이음수인사이클이있는그래프에서는어떤알고리즘도동작하지않음 최장거리문제를최단거리문제로바꿔풀수없는이유
Bellman-Ford s Shortest Path 최단거리의상한값을예측한후실제값과의오차를반복적으로줄여나간다 시작할때 그래프의구조에대해아는것이없다 s 를제외한모든정점에대해upper[u] = INF
Bellman-Ford s Shortest Path 완화 (relaxation) 에의한upper 의갱신 최단거리배열d[] 의성질을이용하자 d [ v] d[ u] + wu (, v) 가중치의완화 v] > upper [ upper[ u] + wu (, v) 라고하자 upper [ v] = upper[ u] + wu (, v) 로바꾸면좀더현실적! 이완화를종료시까지모든간선에대해반복
종료조건및정당성증명 임의의정점 u 까지의최단경로 : 간선의개수는최대 V-1 개 (s,a,b,c,u) 가최단경로라고하자 (s,a,b,c), (s,a,b), (s,a) 들은각각최단경로가된다 모든간선에대해한번완화하면, d[a] = 최단경로임은확실하다 두번하면 d[b] = 최단경로 세번하면 d[c] = 최단경로 V-1 번하면모든정점에대해 d[] = 최단경로
음수간선및음수사이클 그래프에음수사이클이있다면, 영원히완화가성공할수밖에없다 완화실패조건 upper[ a] upper[ s] + 10 upper[ b] upper[ a] 21 upper[ s] upper[ b] + 10 좌변과우변을모두더하면 upper[ a] + upper[ b] + upper[ s] upper[ a] + upper[ b] + upper[ s] 1 따라서완화는정지할수없다 V 번째완화가성공할경우, 음수사이클이존재
Bellman-Ford Algorithm: 구현 int V; int adj[max_v][max_v]; int upper[max_v]; // Negative Cycle 이있을경우 false 를반환 bool bellmanford(int src) { for(int i = 0; i < V; ++i) upper[i] = INF; upper[src] = 0; for(int i = 0; i < V-1; ++i) for(int here = 0; here < V; ++here) for(int there = 0; there < V; ++there) upper[there] = min(upper[there], upper[here] + adj[here][there]); for(int here = 0; here < V; ++here) for(int there = 0; there < V; ++there) if(upper[there] > upper[here] + adj[here][there]) return false; return true; } 보너스로음수사이클존재여부도찾아줌 시간복잡도 : O(VE)
Dijkstra s Shortest Path 데익스트라 라고읽는것같아요. 2002 년작고하신네덜란드의전산학자 BFS 를뼈대로하는최단거리알고리즘 가중치가있는그래프의BFS 라고보면됩니다 시작점에서부터가까운순서대로방문해나간다 각정점마다지금까지본최단경로의길이를저장 더짧은경로가나타날때마다해당길이를업데이트 이기록이작은정점부터방문해나간다
실제로동작을봅시다 평범한그래프 G 군
실제로동작을봅시다 시작점까지의최단거리는항상 0 이란것을안다 ( 최단거리확정 ) 5 인간선을따라가고, 1 인간선을따라가서각각현재까지의최단거리를쓴다
실제로동작을봅시다 숫자가쓰인정점중가장작은정점을골라방문한다 ( 최단거리확정 ) 초록색에서간선을따라가면빨간색까지길이가 3 인경로를얻을수있다
실제로동작을봅시다 초록색까지의거리가 3 인것을알았으므로, 빨간색까지길이가 4 인경로를얻을수있다 지금까지는 5 가씌여있었으니까, 쓰인숫자를바꾼다
실제로동작을봅시다 초록색까지의거리가 4 인것을알았으므로, 빨간색까지길이가 7 인경로를얻을수있다
실제로동작을봅시다 초록색까지의거리가 6 인것을확정. 초록색을통해길이 8 인경로를얻을수있지만, 빨간색까지는이미길이 7 인경로를알고있으므로무시한다
실제로동작을봅시다
실제로동작을봅시다
어떻게구현할까? BFS 를기준으로하되, 우선순위큐를사용한다 1 차원배열 D[] 에각정점별로현재까지발견한최단거리를저장한다 큐에있는정점중, D[] 가가장작은정점을꺼내방문한다 인접정점중아직방문하지않은곳들의 D[] 를업데이트한다
Priority Queue 우선순위 순서대로원소들이꺼내지는큐 큐의각원소들은 ( 우선순위, 자료 ) 의쌍으로이루어진다 힙(Heap), 이진검색트리등으로구현가능 메모리로컬리티등의이유로대개힙으로구현 CLRS 6장, 힙정렬참조 대개 std::priority_queue 를쓴다
Dijkstra s Shortest Path BFS 에서사용하는큐대신우선순위큐를사용한다 ( 작을수록먼저나오는큐 ) 우선순위큐에는 (- 시작점으로부터의거리, 정점번호 ) 의쌍이들어간다 D[] 가변화할때큐는어떻게할것인가?
Dijkstra s Shortest Path A 가방문된시점에서, (10, b) 와 (4, c) 가큐에들어간다. C 를방문하면, 우리가b 까지의최단거리가10 이라고생각하고있었는데9 로바뀐다 어떻게할까?
Dijkstra s Shortest Path 1. (10,b) 를큐에서찾아서 (9,b) 로줄인다 이진힙에서하기힘든연산 이진검색트리나피보나치힙을사용하면가능하다 2. (9,b) 를하나더넣는다 큐에 (9,b)(10,b) 가순서대로들어간다 이쪽이더자주사용하는방법
Dijkstra s Shortest Path: 구현 int V; vector<pair<int int, int> > adj[max_v]; int C[MAX_V]; 중복원소의처리 pair<int,int> 의사용 void dijkstra(int int src) { for(int i = 0; i < V; ++i) D[i] = INF; C[src] = 0; priority_queue<pair<int int, int> > pq; pq.push(make_pair(0, src)); while(!pq.empty()) { int cost = -pq.top().first; int here = pq.top().second; pq.pop(); if(c[here] < cost) continue ntinue; for(int i = 0; i < adj[here].size(); ++i) { int there = adj[here][i].first; int nextcost = cost + adj[here][i].second; if(c[there] > nextcost) { C[there] = nextcost; pq.push(make_pair(-nextcost, there)); } } } }
Dijkstra s Shortest Path: 증명 종료시에 D[i] = i 까지의최단거리인가? 루프불변조건을이용한귀납법 루프불변조건 (Loop Invariant) 알고리즘의실행중에항상성립하는하나의조건 초기성립, 유지속성을증명한다 ( 일종의귀납법 )
Dijkstra s Shortest Path: 증명 루프불변조건 모든방문한정점에대해 D[i] 는 i 까지의최단거리 초기조건 D[start] = 0 유지조건 새로방문한정점 u 에대해 D[u] = u 까지의최단거리 ( 이것을보이는것이루프불변조건을이용한증명의포인트!)
Dijkstra s Shortest Path: 유지조건증명 이번에정점 u 를방문했다고하자 u 이전의모든방문한정점들에대해 d[x] = 최단거리 d[u] > 최단거리가되려면어떻게되어야할까? v 는이경로중방문하지않은최초의정점 (a,, q, v,..,u) 가최단경로라면 (a,, q, v) 도최단경로다. 그러면 d[v] = 최단거리! 그러나 u 를방문한다는말은 d[u] < d[v]. d[v] + alpha > d[u] 면모순
Dijkstra s Shortest Path: 음수가중치 w(v,u) 가음수라면, w[v] > w[u] 라도최단거리일수있다 따라서음수가중치가있는그래프일경우 Dijkstra 알고리즘은최단거리를찾아주지못한다
Dijstra s Algorithm: O(V 2 ) 구현 void dijkstra2(int int src) { for(int i = 0; i < V; ++i) C[i] = INF; vector<bool bool> visited(v, false); C[src] = 0; visited[src] = true; for(int i = 0; i < V-1; ++i) { int closest = INF, here; for(int j = 0; j < V; ++j) if(c[j] < closest &&!visited[j]) { here = j; closest = C[j]; } visited[here] = true; for(int j = 0; j < adj[here].size(); ++j) { int there = adj[here][i].first; if(visited[there]) continue; int nextcost = closest + adj[here][j].second; C[there] = min(c[there], nextcost); } } } 별도의우선순위큐를사용하지않는구현
Floyd s Algorithm 모든쌍의최단거리를찾아주는동적계획법알고리즘 int V; int adj[max_v][max_v]; void floyd() { for(int k = 0; k < V; ++k) for(int i = 0; i < V ++i) for(int j = 0; j < V; ++j) adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); } 이걸로끝이에요! 어떻게이렇게간단한알고리즘이나올까요?
Backgrounds 정점 u, v 간의최단경로는 V 안의어떤점도거쳐갈수있다 D S ( u, v) = S 에포함된정점만을거쳐가는최단거리 Then, D V ( u, v) = u 에서v 까지의최단거리 ( u, v) = u 와v 를잇는간선의길이 ( 없으면 ) D φ x S 라고하자. u~v 는x 를거칠까안거칠까? D S ( u, v) = DS { x} ( u, x) + DS { min DS { x} ( u, v) x} ( x, v)
그렇다면.. = 만을거쳐가는최단경로 = Backgrounds ), ( ' v u D k ), }(,,, { 2 1 v u D k v v v L },,, { 2 1 k v v v L 라고정의하자. 그러면 : + = ), ( ), ( ), ( min ), ( } { } { } { v u D v x D x u D v u D x S x S x S S + = ), ( ' ), ( ' ), ( ' min ), ( ' 1 1 1 v u D v v D v u D v u D k k k k k k
Floyd 프로토타입 int V; int adj[max_v+1][max_v+1]; int D[MAX_V+1][MAX_V+1][MAX_V+1]; ( 유의 : 이코드에서정점들은 1,2,3,,V 의번호를가진다 ) void floyd_prototype() { for(int i = 1; i <= V; ++i) for(int j = 1; j <= V; ++j) D[0][i][j] = adj[i][j]; for(int k = 1; k <= V; ++k) for(int i = 1; i <= V; ++k) for(int j = 1; j <= V; ++j) D[k][i][j] = min(d[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]); } D[0][i][j] = 중간정점을하나도안거치는최단거리 D[k][i][j]= { 1, 2,, k } 을거치는최단거리
Floyd 프로토타입 D[k][i][j] = min( D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j] ); 이때 D[k-1][i][k] = D[k][i][k] D[k-1][k][j] = D[k][k][j] 왜냐면, i~k 경로나 k~j 경로는반드시 k 를들리기때문이다
그래서 이와같은 O(V^2) 공간복잡도를갖는코드가됩니다 int V; int adj[max_v][max_v]; void floyd() { for(int k = 0; k < V; ++k) for(int i = 0; i < V ++i) for(int j = 0; j < V; ++j) adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); } (u,v) 간에간선이없을경우 adj[u][v] = INF 로초기화
모델링 현실세계의문제로부터그래프형태로표현가능한모델을만드는것 명시적인그래프에선쉽고 암시적인그래프에선어렵겠죠
Knight Tour 양쪽다나이트로상대방킹을잡으러간다고하자. 어느쪽이먼저체크할수있을까? 백의차례라고가정
Knight Tour 양쪽다나이트로상대방킹을잡으러간다고하자. 어느쪽이먼저체크할수있을까? 백의차례라고가정 그래프의각칸을정점으로, 나이트의이동을간선으로하는그래프를만든후 BFS
변신체스 백의킹을움직여체크하고싶다 흑은움직이지않는다고가정 무늬가새겨진칸에가면해당칸에그려진말의색으로변신할수있다 변신후에도변신능력은유지한다 몇턴지나야체크할수있나?
변신체스 같은칸에있더라도, 현재어떤말의모양을하고있느냐에따라상태가다르다 ( 현재위치, 현재말 ) 의쌍이하나의정점이되고, 현재말의종류에따라간선의형태가달라지는그래프 이그래프에서의최단거리로체크까지필요한턴수를알수있다
지하철노선도 모든구간이 2 분걸린다고가정하면, 강남에서월드컵경기장을가기위한가장짧은경로는? (trivial)
지하철노선도 ( 환승시간 ) 환승에 5 분씩이걸린다고하면가장짧은경로는어떻게변할까?
지하철노선도 ( 환승시간 ) 2 호선교대역과 3 호선교대역을별개의정점으로분리합시다
운송문제 A 에서 I 로물건을배달하고싶다 각도로를지나는데는통행료가든다 통행료를최소화하는경로는?
운송문제 w/ 도시별통행료 각도시들이통행료를걷기시작했다 : 어떻게풀수있을까?
운송문제 w/ 도시별통행료 통행료는도시에들어갈때낸다 : incoming edge 의가중치에더해준다 무방향그래프에서방향그래프로변한다
운송문제 w/ 여러개의시작위치 a, b, c 어느곳에서도시작할수있다. Single-Source 최단거리알고리즘여러번하지않고풀수있는방법이있을까?
운송문제 w/ 여러개의시작위치 슈퍼소스 (supersource) s 를추가하고, a, b, c 까지가중치 0 인간선을추가한다 a, b, c 에서 s 로돌아갈수있으면안된다!
운송문제 w/ 제한속도 각도로에는제한속도가있다 ( 이속도로만다녀야한다 ) 가속하거나감속하는데는연료가든다 2 ( prevspeed newspeed) 연료소모를최소화할수있는경로는? 초기속도는 10 이라고하자.
운송문제 w/ 제한속도 각정점을해당정점에서가질수있는속도별로쪼갠다 일반적인최단경로문제가된다
Multiplicative Shortest Path 신호가특정선로를지날때마다노이즈가 x 배증가한다. 노이즈를최소화할수있는경로는?
Simple Shortest Path 로해결가능! log( a b c d) = loga+ logb+ logc+ logd 각간선의 log 를취해주면최단거리로풀수있다 사실, 로그를취할필요도없이 Dijkstra 를그대로적용할수있다
Arctic Networks R 만큼떨어진두기지가통신하려면, 출력이 R/2 이상이어야한다 모든기지는같은무전기를쓴다 a 가모든기지와통신할수있기위한최소출력은?
Arctic Networks R 만큼떨어진두기지가통신하려면, 출력이 R/2 이상이어야한다 모든기지는같은무전기를쓴다 a 가모든기지와통신할수있기위한최소출력은?
Arctic Networks 최단거리알고리즘을그대로적용가능 Dijkstra, Floyd, Bellman-Ford 어느것을써도좋다 최단거리 => 최대거리로의변환이알고리즘의정당 성을유지한다는것을알려면, 알고리즘의동작원리에대해이해하고있어야한다 그외에도많은답 Kruskal s MST (CLRS 23 장 ) Binary Search + DFS
운송문제 w/ 최대 - 최소속도 각도로에서는제한속도를지켜야한다 운송물은불안한화학약품 최소속도와최대속도의차이를가장작게하는경로를찾고싶다