Graph Optimization Problems and Greedy Algorithms

Optimization Problem

• 최적해 (Optimal Solution) : Minimizing the total costs or Maximizing the total benefits
• Anaylyze all possible outcomes
• Make a series of choices -> Effect is to achieve the optimal

 

Greedy Algorithms

• Making choices in sequence such that
  1. Each individual choice is the best
  2. Once a choice is made, it cannot be undone
• Possible drawback : Actions with a small short-term cost may be lead to a situation, where further large costs are unavoidable

 

Graph Optimization Problems Solved by the Greedy Algorithm

1. Minimum cost for connecting all vertices -> Minimum Spanning Tree Algorithm
2. Shortest path between two vertices -> Single-Source Shortest Paths Algorithm

 

Minimum Spanning Tree

• Spanning Tree : Acyclic connected subgraph of $G$
• Minimum Spanning Tree : A spanning tree with the minimum weight
• Input : Weighted Graph
• Output : Minimum Spanning Tree
• Spanning Tree of (a) : (b), (c), (d)
• Minimum Spanning Tree of (a) : (b), (c)

Spanning Tree of weighted graph (a)

 

Prim's Algorithm

• Tree를 점점 키워나가는 Algorithm
• Strategy
  1. Select an arbitrary starting vertex (the root)
  2. Attach the minimum weighted edge at each iteration that can be attached
  3. Add to the tree the vertex associated with the edge
• Vertices are divided into three disjoint categories
  1. Tree vertices : in the tree constructed so far
  2. Fringe vertices : not in the tree, but adjacent to some vertex in the tree
  3. Unseen vertices : all others
• Implement by priority queue using an unsorted array
• $O(n^2)$ : Dependent of # of vertices

PrimMST(G, n) // G = (V, E), # of V = n, # of E = m
	Initialize all vertices an unseen;
	Select an arbitrary vertex s to start the tree;
	Reclassify it as tree;
	Reclassify all vertices adjacent to s as fringe;
	while there are fringe vertices
		Select an edge of minimum weight 
			between a tree vertex t and a fringe vertex v
		Reclassify v as tree; add edge tv to the tree
		Reclassify all unseen vertices adjacent to v as fringe

 

Kruskal's Algorithm

• Data structure for Kruskal's algorithm : Union-Find
  1. The algorithm maintains a forest of trees
  2. $find(u)$ : Return the set storing $u$
  3. $union(u, v)$ : Replace the sets storing $u$ and $v$ with their union
• Heuristic of Union-Find ADT
  1. Weighted union heuristic : 원소 수가 더 많은 Set에 원소 수가 더 적은 Set을 붙임
  2. Path compression heuristic : 집합 내 한 원소에서 루트를 찾는 과정을 압축
• $O(m \log{m})$ : Dependent of # of edges

KruskalMST(G, n)
	R = E // R is remaining edges
	F = Ø // F is forest edges
	while R is not empty
		Remove the lightest, shortest edge, vw, from R;
		if vw does not make a cycle in F
			Add vw to F;
	return F;

Path compression heuristic

 

Single-Source Shortest Path

• Problem : Find a minimum-weight path between tweo specified vertices
• Definition : If no path between $x$ and $y$ has weight less than $W(P)$ -> $P$ is called a shortest paht
• Lemma : Shortest Path Property (귀류법을 통해 증명)
  1. A shortest path from $x$ to $z$ consists of path $P$ from $x$ to $y$ followed by path $Q$ from $y$ to $z$
  2. $P$ is a shortest path from $x$ to $y$
  3. $Q$ is a shortest path from $y$ to $z$
• 귀류법을 통한 Lemma 증명
  
  1. " $R$은 최단 경로이면 $R$을 구성하는 $P$와 $Q$ 또한 최단 경로이다"라는 명제의 결론을 부정해 보자.
  2. 그렇다면 $P$와 $Q$가 최단 경로가 아니므로, 또 다른 간선인 $P'$와 $Q'$가 최단 경로이다.
  3. 이 경우 $R = P + Q \ge P' + Q'$이므로 $R$이 최단 경로라는 가정에 모순이 발생하므로 해당 명제는 참임을 알 수 있다.

귀류법을 통한 Lemma 증명

 

Dijkstra's Shortest-Path Algorithm

• 다엑스트라 알고리즘은 $1:N$ problem solution으로 Greedy Algorithm을 사용한다.
• 최단 거리를 찾기 위한 그래프의 조건으론 가중치가 $0$ 이상의 값이어야 한다.

dijkstraSSSP(G,n)
	Initialize all vertices as unseen;
	Start the tree with the specified source vertex s;
	Reclassify it as tree;
	Define d(s,s) = 0; // d(a,b) : the shortest distance from a to b
	Reclassify all vertices adjacent to s as fringe;
	while there are fringe vertices:
		Select an edge between a tree vertex t and a fringe vertex v
			such that d(s,t) + W(tv) is minimum
		Reclassify v as tree; Add edge tv to the tree;
		Define d(s,v) = d(s,t) + W(tv);
		Reclassify all unseen vertices adjacent to v as fringe;

 

Transitive Closure

• Transitive Closure of $G$ : $G^*$
• $G^*$는 $G$와 같은 정점을 갖고 있다.
• 만약 $G$에서 $u$부터 $v$까지의 경로가 존재한다면 $(u \neq v)$, $G^*$에선 $u$와 $v$를 연결하는 간선이 존재한다.
• Transitive Closure는 한 정점으로부터 다른 정점까지 도달할 수 있는가에 대한 정보를 갖고 있다.

Transitive Closure of G

 

Floyd-Warshall Transitive Closure

• Input : Digraph $G$
• Output : Transitive Closure $G^*$ of $G$
• Running time : $O(n^3)$, assuming areAdjacent is $O(1)$ (Implement by Adjacency Matrix, 인접 행렬)

Sudo code of Floyd-Warshall algorithm

 

All-Pairs Shortest Paths

• Find the distance between every pair of vertices in a weighted directed graph $G$ ($N : N$ Problem)
• Can be solved by $N$ calls to Dijkstra's algorithm, which takes $O(nm \log{n})$ time
• Can achieve $O(n^3)$ time using dynamic programming

Sudo code of the algorithm for finding all-pairs shortest paths