제9장 그래프 알고리즘

(1)

http://academy.hanb.co.kr

쉽게 배우는 알고리즘

9장. 그래프 알고리즘

IT COOKBOOK IT COOKBOOK

9장.

그래프 알고리즘

수학은 패턴의 과학이다. 음악 역시 패턴들이다. 컴퓨터 과학은 추상화와 패턴의 형성에 깊은 관련이 있다. 컴퓨터 과학이 다른 분야들에 비해 특징적인 것은 지속적으로 차원이 급상승한다는 점이다. 미시적 관점에서 거시적 관점으로 도약하는 것이다. -도널드 크누스

(2)

- 3 - 숙명여자대학교 멀티미디어과학과

학습목표

• 그래프의 표현법을 익힌다. • 너비우선탐색과 깊이우선탐색의 원리를 충분히 이해하도록 한 다. • 신장트리의 의미와 최소신장트리를 구하는 두 가지 알고리즘을 이해한다. • 그래프의 특성에 따라 가장 적합한최단경로 알고리즘을 선택할 수 있도록 한다. • 위상정렬을 이해하고 DAG의 경우에 위상정렬을 이용해 최단경 로를 구하는 방법을 이해한다. • 강연결요소를 구하는 알고리즘을 이해하고 이 알고리즘의 정당 성을 확신할 수 있도록 한다. • 본문에서 소개하는 각 알고리즘의 수행시간을 분석할 수 있도록 한다. IT COOKBOOK IT COOKBOOK

Graph

• 현상이나 사물을 정점(vertex)

과 간선(

edge)으로

표현한 것

• Graph G = (V, E)

– V: 정점 집합

– E: 간선 집합

• 두 정점이 간선으로 연결되어 있으면

인접하다고 한다

– 인접 = adjacent

– 간선은 두 정점의 관계를 나타낸다

(3)

그래프의 예

영희 철수 준호 동건 승우 재상

사람들간의 친분 관계를 나타낸 그래프

(두 도시 간 도로 존재 여부, 두 집안 간의 혼인 여부 등) IT COOKBOOK IT COOKBOOK 영희 철수 준호 동건 승우 재상 9 7 5 6 9 5 1 5

친밀도를 가중치로 나타낸 친분관계 그래프

(도시들 간의 거리, 두 지점 사이에 묻힌 가스 파이프의 용량, 두 공항 사이의 비행 시간 등)

(4)

- 7 - 숙명여자대학교 멀티미디어과학과 영희 철수 준호 동건 승우 재상

방향을 고려한 친분관계 그래프

(각 사람이 다른 사람에게 애정을 가지고 있는가, 기업들 간의 제품 공급 관계, 제품 생산 공정에서 의 선후 관계 등)

유향 그래프directed graph=digraph

IT COOKBOOK IT COOKBOOK 영희 철수 준호 동건 승우 재상 9 7 5 6 9 5 1 5 8 8 2 6

가중치를 가진 유향 그래프

(누가 누구를 얼마만큼 좋아하는지, 서울과 LA간 비행기 노선에서 가는 데 걸리는 시간과 오는 데 걸리는 시간이 다른 경우)

(5)

2. Graph의 표현 1: Adjacency Matrix

• 인접 행렬(Adjacency Matrix)

– N x N

행렬로 표현 • 원소 (i, j) = 1 : 정점 i 와 정점 j 사이에 간선이 있음 • 원소 (i, j) = 0 : 정점 i 와 정점 j 사이에 간선이 없음 – 유향 그래프의 경우 • 원소 (i, j)는 정점 i 로부터 정점 j 로 연결되는 간선이 있는지를 나타냄 • 원소(i, j)와 원소 (j, i)가 대칭적이지 않음 – 가중치 있는 그래프의 경우 • 원소 (i, j)는 1 대신에 가중치를 가짐 N

: 정점의 총 수

IT COOKBOOK IT COOKBOOK 영희 철수 준호 동건 승우 재상 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 6 5 4 3 2 1 2 3 4 5 6 1 2 3 4 5 6

무향 그래프의 예

(6)

- 11 - 숙명여자대학교 멀티미디어과학과 영희 철수 준호 동건 승우 재상 0 9 7 5 0 6 9 0 9 0 0 0 7 9 0 0 5 0 5 0 0 0 0 5 0 0 5 0 0 1 6 0 0 5 1 0 1 6 5 4 3 2 1 2 3 4 5 6 1 2 3 4 5 6 9 7 5 6 9 5 1 5

가중치 있는 무향 그래프의 예

IT COOKBOOK IT COOKBOOK 0 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 6 5 4 3 2 1 2 3 4 5 6 1 2 3 4 5 6 영희 철수 준호 동건 승우 재상

유향 그래프의 예

(7)

- 13 - 숙명여자대학교 멀티미디어과학과 0 8 7 5 0 6 9 0 6 0 0 0 0 9 0 0 5 0 8 0 0 0 0 5 0 0 0 0 0 2 0 0 0 0 1 0 1 6 5 4 3 2 1 2 3 4 5 6 1 2 3 4 5 6 영희 철수 준호 동건 승우 재상 9 7 5 6 9 5 1 5 8 8 2 6

가중치 있는 유향 그래프의 예

유향 그래프의 다른 예

(8)

가중치 있는 그래프의 다른 예

Adjacency Matrix 표현법의 장단점

• 장점

– 이해하기 쉽고, 간선 존재 여부를 즉각 알 수 있음

• 단점

– n

2

_{에 비례하는 공간 필요}

– 행렬의 모든 원소를 채우는 데에만 n

2

_{에 비례하는}

시간 필요

• 간선의 밀도가 높은 그래프에서는 유리

– 정점이 100만개인데 간선이 200만개 밖에 없다면?

(9)

• Adjacency list

– N 개의 연결 리스트로 표현 – i 번째 리스트는 정점 i 에 인접한 정점들을 리스트로 연결해 놓음 – 가중치 있는 그래프의 경우 • 리스트는 가중치도 보관한다

2. Graph의 표현 2: Adjacency List

IT COOKBOOK IT COOKBOOK 영희 철수 준호 동건 승우 재상 1 6 5 4 3 2 1 2 3 4 5 6 2 3 4 6 1 3 1 2 5 1 6 3 6 1 4 5

무향 그래프의 예

정점 번호 v 무향 그래프에서 필요한 총 노드 수는 존재하는 총 간선 수의 두 배 v 유향 그래프에서는 간선 하나당 노드 하나씩 필요

(10)

- 19 - 숙명여자대학교 멀티미디어과학과 영희 철수 준호 동건 승우 재상 1 2 3 4 5 6 9 7 5 6 9 5 1 5 1 6 5 4 3 2 2 9 3 7 4 5 6 6 1 9 3 9 1 7 2 9 5 5 1 5 6 5 3 5 6 1 1 6 4 5 5 1

가중치 있는 그래프의 예

<정점 번호,가중치,다음 정점 포인터>로 구성된 노드 IT COOKBOOK IT COOKBOOK

Adjacency List 표현법의 장단점

• 장점

– 간선 총 수에 비례하는 양만큼만 필요

– 모든 가능한 정점 쌍에 비해 간선 수가 적을 때 유리

• 단점

– 거의 모든 정점에 간선이 있는 경우 리스트 생성에

큰 오버헤드가 듦.

– 정점 i와 j 간에 간선이 있는지 알아볼 때 시간이

많이 걸림

(11)

3. Graph Traversal

• 대표적 두가지 방법

– 너비우선탐색(BFS, Breadth-First Search)

– 깊이우선탐색(DFS, Depth-First Search)

• 너무나 중요함

– 그래프 알고리즘의 기본

– DFS/BFS는 간단해 보이지만 제대로 아는 사람은

매우 드물다

– DFS/BFS는 뼛속 깊이 이해해야 좋은 그래프

알고리즘을 만들 수 있음

동일한 트리를 각각 DFS/BFS로 방문하기

DFS

BFS

(12)

- 23 - 숙명여자대학교 멀티미디어과학과 1 (a) 1 4 3 2 (b) 1 7 4 3 6 5 2 (c) 1 7 4 3 6 5 2 8 (d) 1 7 4 3 6 5 2 8 (e)

그래프에서의 BFS 작동 예

v 검은색 굵은 간선: 각 정 점 을 처 음 방문할 때 사용한 간선 v 굵 은 간 선 들 만 남 기 면 트 리 가 되는데 이 트리를 너비우선트리라 함 IT COOKBOOK IT COOKBOOK

BFS 알고리즘

BFS(G, v) { for eachv∈V – {s} visited[v] = NO; ▷ 시작 정점을 뺀 모든 정점들을 방문하지 ▷ 않았음으로 표시 visited[s] = YES; ▷ 시작 정점 enqueue(Q, s); ▷ 이미 방문한 정점들을 큐에 넣는다. while(Q ≠Ø) { u = dequeue(Q);

for eachv∈L(u) ▷ L(u): 정점 u의 인접리스트 if(visited[v] == NO) then

visited[u] = YES; ▷ 방문하였음 이라고 표시 enqueue(Q, v);

} }

(13)

- 25 - 숙명여자대학교 멀티미디어과학과 1 (a) 1 2 (b) 1 3 2 (c) 1 3 2 4 (d) 1 3 2 5 4 (e)

그래프에서의 DFS 작동 예

1 3 2 6 5 4 (f) IT COOKBOOK IT COOKBOOK 1 3 2 6 5 7 4 (g) 1 3 2 6 5 7 8 4 (h) 1 3 2 6 5 7 8 4 (i)

그래프에서의 DFS 작동 예 (계속)

깊이우선트리

(14)

DFS 알고리즘

DFS(G) { for eachv∈V visited[v] ← NO; for eachv ∈ V

if(visited[v] == NO) thenaDFS(v); }

aDFS(v) {

visited[v] = YES;

for eachx∈L(v) ▷ L(v): 정점 v의 인접 리스트

if(visited[x] == NO) thenaDFS(x); }

ü수행시간: Θ(V+E)

4. 최소 신장 트리

• 무향 그래프 G의 신장트리(Spanning Tree)

– 무향 그래프 G = (V, E)에서 정점 집합 V는 그대로

두고 간선을 |V|-1 개만 남겨 트리가 되도록 만든 것.

• 최소신장트리(Minimum Spanning Tree)

– 간선들이 가중치를 갖는 그래프에서 간선 가중치의

합이 가장 작은 트리

• 용도: 최소 비용을 사용하여 네트워크 망을

구축하고 싶을 때.

(15)

- 29 - 숙명여자대학교 멀티미디어과학과 Prim (G, r) ▷ G = (V, E): 주어진 그래프 ▷ r: 시작 정점 { S = Ø ; ▷ S: 최소신장트리에 포함될 정점들의 집합 정점 r을 방문되었다고 표시하고, 집합 S에 포함시킨다; while(S≠V) { S에서 V-S를 연결하는 간선들 중 최소길이의 간선 (x,y) 를 찾는다; ▷ (x∈S, y∈V-S) 정점 y를 방문되었다고 표시하고, 집합 S에 포함시킨다; } } ü Prim 알고리즘은 그리디greedy알고리즘의 일종 ü 그리디 알고리즘으로 최적해를 보장하는 드문 예

Prim Algorithm

IT COOKBOOK IT COOKBOOK 0 11 8 9 8 8 ∞ 9 ∞ ∞ 13 10 5 12 7 11 (b) _S 8 9 8 ∞ ∞ ∞ ∞ ∞ ∞ 0 10 5 13 12 7 11 (a) r 11 12 8 8 5 9 ∞ 0 10 5 13 12 7 11 9 (d) S

Prim Algorithm의 작동 예

11 9 8 8 10 9 ∞ ∞ 0 10 5 13 12 7 11 8 (c) S : 방금 S에 포함된 정점 : 신장트리. 점점 커짐.

(16)

- 31 - 숙명여자대학교 멀티미디어과학과 11 12 8 8 5 9 ∞ 0 13 12 7 11 8 9 8 7 0 10 7 11 5 (e) (h) S 11 8 9 8 7 0 10 12 7 8 (g) S S 11 12 8 8 9 8 0 5 12 7 11 (f) S 11 8 9 8 7 0 5 (i) IT COOKBOOK IT COOKBOOK Prim (G, r) ▷ G = (V, E): 주어진 그래프 ▷ r: 시작 정점 { S = Ø ; ▷ S: 최소신장트리에 포함될 정점들의 집합 for each u ∈ V d[u] = ∞; ▷ d[u]: 각 정점을 신장트리에 포함시키는 데 드는 최소비용을 계산하기 위한 것 d[r] = 0; ▷ r 정점을 mst에 포함시키는 데에는 비용이 안 들었음. while (S ≠ V) { ▷ 모든 정점들을 순회한다. 정점이 n개이면 n회 반복 u = extractMin(V – S, d); S = S∪ {u};

for each v ∈ L(u) ▷ L(u): u의 인접 정점 집합

if (v ∈ V-S && w(u, v) < d[v]) { d[v] = w(u, v); tree[v] = u; ▷ 현재까지 계산 결과 정점 v를 신장트리에 연결시키는 비용이 } ▷ 가장 적게 드는 간선(맞은 편 정점)을 저장. } } extractMin(Q, d[]) { 집합 Q에서 d 값이 가장 작은 정점 u를 리턴한다. } Prim Algorithm – 구체적 버전 ü수행시간: O(ElogV)

(17)

- 33 - 숙명여자대학교 멀티미디어과학과 Kruskal (G) { T ← Ø; ▷ T: 신장트리 단 하나의 정점만으로 이루어진 n 개의 집합을 초기화한다; 모든 간선을 가중치가 작은 순으로 정렬하여 배열 A[1…E]에 저장한다; while (T의 간선수 < n-1) { A에서 최소비용 간선 (u, v)를 제거한다; if (정점 u와 정점 v가 서로 다른 집합에 속함) { T ← T∪{(u, v)}; 두 집합을 하나로 합친다; } } }

Kruskal Algorithm

ü수행시간: O(ElogV) IT COOKBOOK IT COOKBOOK 8 9 8 10 5 13 12 7 11 (a) 8 (b) 8 9 8 10 13 12 7 11 8 (c) 8 9 8 10 13 12 11 8 (d) 9 8 10 13 12 11 8

Kruskal Algorithm의 작동 예

(e) 9 10 13 12 11 8 : 방금 고려한 간선

(18)

- 35 - 숙명여자대학교 멀티미디어과학과 (i) 8 9 8 5 7 11 (h) 13 12 (g) 10 13 12 11 (f) 10 13 12 11 9 v 양 끝점이 같은 집합에 속해 이 간선을 넣으면 싸이클이 형성된다. 이 간선은 버린다. IT COOKBOOK IT COOKBOOK

Kruskal Algorithm 분석

• 싸이클을 만들지 않으면서 최소 비용 간선을 하나씩

더해가며 최소신장트리를 만듦.

• Prim이 하나의 트리를 키워 나가는 방식이라면,

크루스칼은 무조건 최소 간선을 포함시키므로 여러

크리들이 산재해가며 완성되어 간다.

– 부분적 트리들을 조각조각 만들고 합쳐가며 최소신장트리를 만든다.

(19)

• [안전성 정리] 간선이 가중치를 갖는 무방향 그래프

G=(V, E)의 정점들이 임의의 두 집합 S와 V-S로

나누어져 있다고 하자. 간선 (u, v)가 S와 V-S 사이의

최소 교차 간선

이라면 (u, v)를 포함하는 그래프 G의

최소신장트리가 반드시 존재한다.

– 프림 알고리즘 • 이미 구성된 집합 S에서의 최소신장트리에 V-S 사이를 연결하는 최소 간선을 더하는 것은 안전하다. – 크루스칼 알고리즘 • 임의의 간선 (u, v)를 더하는 시점에 (u, v)는 그 때까지 고려되지 않은 모든 간선들 중 최소 간선이다. • 정점 u가 속한 집합을 S라 하면, (u, v)는 집합 S와 나머지 V-S의 최소 교차 간선이다.

Prim & Kruskal 알고리즘의

안전성 정리

5. Topological Sorting

• 목적

– 완수해야 할 여러 가지 일들이 있고,

– 이들 간에 상호 선후 관계가 있다.

• 목적 달성 방법

– 싸이클이 없는 유향 그래프를 이용한 위상 정렬

• Topological Sorting

위상정렬

– 모든 정점을 일렬로 나열하되,

– 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시

y보다 앞에 위치한다.

– 일반적으로 임의의 유향 그래프에 대해 복수의

위상 순서가 존재한다.

(20)

이 그래프에 대한 위상정렬의 예 2개

IT COOKBOOK IT COOKBOOK topologicalSort1(G) { fori ← 1 ton { 진입간선이 없는 정점u를 선택한다; A[i] ← u; 정점u와, u의진출간선을 모두 제거한다; } ▷이 시점에 배열A[1…n]에는 정점들을 위상정렬 되어 있다. }

위상정렬 알고리즘 – 직관적 버전

ü수행시간: Θ(|V|+|E|) u 진입간선 진출간선

(21)

- 41 - 숙명여자대학교 멀티미디어과학과 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (a) (b) (c) (d)

위상정렬 알고리즘 1의 작동 예

IT COOKBOOK IT COOKBOOK 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 남비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (e) (f) (g) ü 제거된 정점의 순서가 가능한 위상정렬 중 하나의 결과임

(22)

- 43 - 숙명여자대학교 멀티미디어과학과 topologicalSort2(G) { for each v∈V visited[v] = NO; for each v∈V ▷정점의 순서는 아무 순서나 무관

if (visited[v] == NO) then DFS-TS(v) ; }

DFS-TS(v) {

visited[v] = YES;

for each x∈L(v) ▷ L(v): v의 인접 리스트

if (visited[x] == NO) then DFS-TS(x) ;

연결 리스트 R의 맨 앞에 정점 v를 삽입한다; }

위상정렬 알고리즘 2 – DFS 버전

ü수행시간: Θ(|V|+|E|) IT COOKBOOK IT COOKBOOK 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (a) (b) (c) (d) 1 1

위상정렬 알고리즘 2의 작동 예

(23)

- 45 - 숙명여자대학교 멀티미디어과학과 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (e) (f) (g) 1 2 3 1 2 1 2 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (h) 3 1 2 4 IT COOKBOOK IT COOKBOOK 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (i) 3 1 2 4 5 냄비에 물붓기 점화 라면넣기 라면봉지 뜯기 계란 풀어넣기 수프넣기 (j) 3 1 2 4 5 6 ü 알고리즘이 끝나고 나면연결 리스트 R에는 그림에서 완료순서의 역순으로정점들이 연결되어 있음 è이 순서가 위상정렬 순서임

(24)

6. 최단 경로(Shortest Paths)

• 조건

– 간선 가중치가 있는 유향 그래프 – 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다.

• 즉, 무향 간선 (u,v)는 유향 간선 (u,v)와 (v,u)를 의미한다고 가정하면 된다.

• 두 정점 사이의 최단경로

– 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로 – 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다. • 가중치가 음수인 것을 허용하더라도 가중치 합이 음인 싸이클은 허용해서는 안 된다는 의미 IT COOKBOOK IT COOKBOOK

• 단일 시작점 최단경로

– 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다. Ø 다익스트라 알고리즘 • 음의 가중치를 허용하지 않는 최단경로 Ø 벨만-포드 알고리즘 • 음의 가중치를 허용하는 최단경로 Ø 싸이클이 없는 그래프의 최단경로

• 모든 쌍 최단경로

– 모든 정점 쌍 사이의 최단경로를 모두 구한다. Ø 플로이드-워샬 알고리즘

• 가중치 팁

– 두 정점간 경로가 존재하지 않으면 이 경로의 길이는 ∞ – 두 정점간 간선이 없으면 가중치가 ∞인 간선이 있다고 간주

최단 경로 알고리즘의 종류

(25)

6.1 Dijkstra Algorithm

Dijkstra(G, r) ▷ G=(V, E): 주어진 그래프 ▷ r: 시작으로 삼을 정점 { S = Ø; ▷ S: 정점 집합

for each u∈V

d[u] = ∞ ; ▷ d[u]: 정점 r에서 정점 u까지 이르는 최단거리

d[r] = 0 ;

while (S ≠ V) { ▷ n회 순환된다.

u ← extractMin(V-S, d) ; S ← S ∪{u};

for each v∈L(u) ▷ L(u) : u로부터 연결된 정점들의 집합

if (v∈V-S and d[v] < d[u]+w(u, v)) then

d[v] = d[u] + w(u, v); } } extractMin(Q, d[]) { 집합 Q에서 d값이 가장 작은 정점 u를 리턴한다 ; } 이완(relaxation) 모든 간선의 가중치는 음이 아니어야 함 ü수행시간: O(|E|log|V|) IT COOKBOOK IT COOKBOOK 0 8 9 8 10 1 3 12 7 11 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 4 5 6 0 11 9 8 8 9 8 10 1 3 12 7 11 8 ∞ ∞ ∞ ∞ 2 4 5 6 ₀ 11 9 18 8 8 10 1 3 12 7 8 ∞ ∞ ∞ 2 4 5 6 0 11 9 10 8 8 12 7 8 12 ∞ ∞ 2 4 5 0 19 11 9 19 10 8 8 12 7 8 12 4 5 6 0 11 9 10 8 8 1 3 12 7 8 ∞ ∞ ∞ 2 4 5 6

Dijkstra Algorithm의 작동 예

(26)

- 51 - 숙명여자대학교 멀티미디어과학과 0 16 11 9 19 10 8 8 9 10 1 3 12 7 11 12 2 4 5 0 16 11 9 19 10 8 12 5 12 0 16 11 9 19 10 8 8 9 10 1 3 12 7 11 12 2 4 5 0 19 11 9 19 10 8 8 12 7 8 12 4 5 6 0 16 11 9 19 10 8 12 IT COOKBOOK IT COOKBOOK

다익스트라 알고리즘이 제대로 동작하지 않는

예 - 가중치에 음수가 있는 경우

0 8 9 8 10 1 3 12 7 11 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 4 5 -15 ₀ 11 9 8 8 9 8 10 1 3 12 7 11 8 ∞ ∞ ∞ ∞ 2 4 5 -15 0 11 9 18 8 8 10 1 3 12 7 8 ∞ ∞ ∞ 2 4 5 -15 0 11 9 10 8 8 1 3 12 7 8 ∞ ∞ ∞ 2 4 5 -15 0 11 9 10 -6 8 1 3 12 7 8 ∞ ∞ ∞ 2 4 5 -15

(27)

다익스트라 알고리즘이 제대로 동작하지 않는

예 - 가중치에 음수가 있는 경우

• 이유

– 임의의 정점을 집합 S에 더할 때 r에서 그 정점까지의 최단 거리는 계산이 끝났다는 확신을 가지고 함 – 만약 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너짐 – 집합 S에 한 번 포함된 정점에 대해서는 최단거리를 다시 계산하지 않으므로 음의 간선은 처리하지 못함 – 만약 집합 S의 내부에 있는 정점에 대해서도 최단 거리를 바꿀 수 있도록 하면? • 그래도 작동 안 됨. IT COOKBOOK IT COOKBOOK BellmanFord(G, r) {

for each u∈V

d[u] = ∞; d[r] = 0;

for i ← 1 to |V|-1 ▷ n-1번 반복함

for each (u, v) ∈ E ▷ d[u]에 변동이 생긴 것만 봐도 됨.

if (d[u] + w(u, v) < d[v] ) then d[v] = d[u] + w(u, v);

▷ 음의 싸이클 존재 여부 확인

for each (u, v) ∈ E

if (d[u] + w(u, v) < d[v] then output “해 없음”; }

6.2 Bellman-Ford Algorithm

이완(relaxation)

음의 가중치를 허용한다

(28)

- 55 - 숙명여자대학교 멀티미디어과학과 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ (a) 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 ∞ 11 9 ∞ ∞ 8 ∞ (b) i = 1 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 19 11 9 19 10 -6 ∞ (c) i = 2 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 19 11 9 12 4 -6 12 (d) i = 3 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 16 11 9 12 4 -6 6 (e) i = 4

Bellman-Ford Algorithm의 작동 예

간선을 최대로 1개 사용하는 최단경로 간선을 최대로 2개 사용하는 최단경로 간선을 최대로 3개 사용하는 최단경로 간선을 최대로 0개 사용하는 최단경로: 초기 상태임 간선을 최대로 4개 사용하는 최단경로 IT COOKBOOK IT COOKBOOK 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 10 11 9 3 4 -6 6 (i) (h) i =7 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 10 11 9 3 4 -6 6 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 10 11 9 3 4 -6 6 (g) i =6 8 9 8 10 1 3 12 -7 11 8 2 4 5 -15 0 10 11 9 9 4 -6 6 (f) i =5 간선을 최대로 5개 사용하는 최단경로 간선을 최대로 6개 사용하는 최단경로 간선을 최대로 7개 사용하는 최단경로 : 변동이 없으므로 간선 7개를 사용하는 최단 경로는 없다는 의미임 완료: 각 정점에 이르는 최단 경로를 형성하는 간선들만 모으면 최단 경로임.

(29)

- 57 - 숙명여자대학교 멀티미디어과학과 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ (a) 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 ∞ 11 9 ∞ ∞ 8 ∞ (b) i = 1 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 19 11 9 19 10 -6 ∞ (c) i = 2 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 19 11 7 12 4 -6 12 (d) i = 3 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 16 10 0 12 4 -8 6 (e) i = 4

음의 싸이클이 있는 그래프에서의

Bellman-Ford Algorithm 동작 예

IT COOKBOOK IT COOKBOOK 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 7 0 -9 3 -5 -18 -3 (i) (h) i =7 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 7 0 -9 3 -5 -18 -3 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 10 3 -3 3 -5 -15 3 (g) i =6 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 10 3 0 9 1 -15 6 (f) i =5 완료: .싸이클 검사 루프를 통과하지 못함

(30)

6.3 모든 쌍 최단 경로 알고리즘 1

BellmanFord 알고리즘 활용기법

-• 정점 한 곳에서 다른 정점들로 가는 최단 경로가 아닌,

• 모든 정점 쌍 사이의 최단 경로를 구해보자.

– 즉, 구해야 할 최단 경로가 모두 n2_{개 이다.}

• 방법 1 – 일반적인 방법(벨만-포드 방법을 활용)

– 변수 dijm: 최대 m개의 간선을 사용해서 정점 i에서 정점 j에 이르는 최단거리 – 점화식 dijm=    == 1 min d_ikm−1 _{+ }    ≥ 2 • 정점 i와 j 사이에 있는 모든 정점 k에 대해, 최대 m-1 개의 간선을 사용한 정점 i와 k 사이의 최단거리 dikm−1 에다, • _를 더한 값을 구한 다음 이들 중 가장 짧은 것을 택한다는 의미 1 ≤ k ≤ n IT COOKBOOK IT COOKBOOK

모든 쌍 최단 경로 알고리즘 1

BellmanFord 알고리즘 활용기법

-simpleShortestPath1(G) ▷ Dynamic Programming 버전

{ for i ← 1 to n for j ← 1 to n dij1 = wij; for m ← 2 to n-1 ▷ 최대 m개의 간선을 사용하는 경우 for i ← 1 to n ▷ i: 시작 정점 for j ← 1 to n ▷ j: 마지막 정점 dijm= min dikm−1 +  ; 1 ≤ k ≤ n ü수행시간: Θ(n4₎

(31)

모든 쌍 최단 경로 알고리즘 2

– Floyd-Warshall Algorithm –

• 같은 DP 이지만 Θ(n

4

_{) è Θ(n}

3

_{)으로 단축시킴}

• 모든 정점들간의 상호 최단거리를 구한다는

목표도 같음

• 응용 예

– Road Atlas

– 네비게이션 시스템

– 네트워크 커뮤니케이션

• 이번에는 변수 d

_ijk

_{가 다음과 같이 정의됨}

– d

_ijk

_{: 정점 집합 {1, 2, …, k}에 속하는 정점들만을}

중간 정점으로 거쳐서 i에서 j에 이르는 최단거리

– 앞에선 사용한 간선의 수와 관련지었지만, 여기선

사용한 정점의 집합과 관계를 지음

– 점화식 d

_ijk

_{= }





  == 0

min d

_ijk−1

_{, d}

ikk−1

+ d

kjk−1

  ≥ 1

모든 쌍 최단 경로 알고리즘 2

– Floyd-Warshall Algorithm –

(32)

• d

_ijk

_{점화식 해석}

– 최단거리 dijk가 형성한 경로를 p라 하자. – Case 1: 만약 경로 p에 정점 k가 포함되어 있지 않으면, 이 경로는 정점 {1, 2, …, k-1}에 속하는 정점만을 사용한다. 즉, dijk= dijk-1임. – Case 2: 만약 경로 p에 정점 k가 포함되어 있다면 정점 k를 중심으로 경로 i ~~> k와 경로 k ~~> j로 나누어보자.

모든 쌍 최단 경로 알고리즘 2

– Floyd-Warshall Algorithm –

i j k 중간정점들이 모두 {1, 2, …, k}에 속함 IT COOKBOOK IT COOKBOOK

• d

_ijk

_{점화식 해석(계속)}

– Case 2(계속)

• 최단 경로 상에 싸이클은 존재할 수 없으므로 두 경로의 중간에 정점 k는 더 이상 나타나지 않는다. 따라서 경로 p는 다음 두 경로의 합에 해당한다. • 정점 집합 {1, 2, …, k-1}에 속하는 정점만을 거치는 최단경로 i ~~> k (길이는 dikk−1) • 정점 집합 {1, 2, …, k-1}에 속하는 정점만을 거치는 최단경로 k ~~> j (길이는 d_kjk−1₎

– Case 1과 Case 2 중 작은 것이 i ~~> j의 최단경로

길이에 해당함.

모든 쌍 최단 경로 알고리즘 2

– Floyd-Warshall Algorithm –

(33)

Floyd-Warshall Algorithm

FloydWarshall(G) { fori ← 1 ton forj ← 1 ton d0 ij← wij; fork ← 1 ton ▷중간정점 집합{1, 2, …, k} fori ← 1 ton ▷ i : 시작 정점 forj ← 1 ton ▷ j : 마지막 정점 dk ij← min {dk-1ij, dk-1ik+ dk-1kj}; } ü dk ij: 중간 정점 집합 {1, 2, …, k}만을 사용하여 정점 i에서 정점 j에 이르는 최단경로 ü 여기서 1, 2, …, n으로 매겨지는 정점의 순서는 상관 없음 ü수행시간: Θ(|V|3₎ IT COOKBOOK IT COOKBOOK

6.4 싸이클이 없는 그래프의 최단경로

• 싸이클이 없는 유향 그래프, DAG

– DAG: Directed Acyclic Graph

• DAG에서의 최단경로

– 모든 정점들을 일렬로 늘어놓을 때, 뒤에 있는

정점에서 앞에 있는 정점으로 가는 간선이 없음

– Topological Sorting을 이용해

선형시간에 간단히

(34)

DAG에서 최단경로 구하기

DAG-ShortestPath(G, r) {

for eachu∈V d[u]= ∞;

d[r] = 0;

G의 정점들을 위상정렬 한다;

for each u∈V (위상정렬 순서로)

for each v∈L(u)▷ L(u) : 정점u로부터 연결된 정점들의 집합 if (d[u] + w(u, v) < d[v] ) thend[v] ← d[u] + w(u, v);

; } ü수행시간: Θ(|V|+|E|) IT COOKBOOK IT COOKBOOK 6 3 -2 -3 1 7 4 5 1 6 3 -2 -3 1 7 4 5 1 (a) (b) 0 6 3 -2 -3 1 7 4 5 1 ∞ _∞ (c) ∞ ∞ ∞ r

DAG-ShortestPath의 작동 예

r 주어진 DAG 초기 상태 위상 정렬 후의 모습 (싸이클 없음) 시작 정점 r을 제외한 나머지 정점의 d[]를 ∞로 초기화 r

(35)

- 69 - 숙명여자대학교 멀티미디어과학과 3 0 ₅ 6 3 -2 -3 1 7 4 5 1 3 0 ₅ 6 3 -2 -3 1 7 4 5 1 (f) (e) 0 6 3 -2 -3 1 7 4 5 1 ∞ _∞ (d) ∞ ∞ ∞ 7 7 ∞ ∞ 7 ∞ 위상 정렬 맨 앞 정점인 s를 택함. 그런데 d[s] 가 ∞이므로 이 루프에선 아무 변화 없음 다음으로 £를 택함. 이로 인해 ™, ♡, r의 d[] 값이 바뀜. 다음으로 ™를 택함. 이로 인해 몇몇 노드의 d[◊] 값 이 바뀜. r r r IT COOKBOOK IT COOKBOOK 3 0 ₂ 6 3 -2 -3 1 7 4 5 1 3 0 ₅ 6 3 -2 -3 1 7 4 5 1 3 0 ₂ 6 3 -2 -3 1 7 4 5 1 (g) (i) (h) ∞ ∞ ∞ ₇ 7 7 5 5 5 ♡를 택한다. d[◊]의 값 이 또 바뀐다. ◊를 택한다. d[r] 값이 바뀜. 최종 결과 모습 r r r

(36)

Strongly Connected Components

• Strongly Connected 유향 그래프

– 그래프의 모든 정점쌍에 대해서 양방향으로 경로가

존재하면 강하게 연결되었다고 한다

– 강하게 연결된 부분 그래프를 강연결요소

Strongly connected component

라 한다

• 문제 정의

– 임의의 그래프에서 강연결요소들을 찾는다.

– 깊이우선탐색의 대표적 응용

강연결요소 구하기 알고리즘

stronglyConnectedComponent(G) { 1. 그래프 G에 대해에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다; 2. G의 모든 간선들의 방향을 뒤집어 GR_{을 만든다;} 3. DFS(GR _{)를 수행하되 시작점은 1에서 구한 f[v]가 가장 큰 정점으로} 잡는다; 4. 3에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다; } ü수행시간: Θ(|V|+|E|)

(37)

- 73 - 숙명여자대학교 멀티미디어과학과 2 1 6 5 7 8 4 3 9 2 1 6 5 7 10 8 4 3 (a) (b) (c) (d) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 GR G G G 9 10 1 2 3 4 5 6 7 8

stronglyConnectedComponent의 작동 예

IT COOKBOOK IT COOKBOOK (e) GR (f) GR (g) GR (h) GR (i) GR 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8

(38)