3-4. DAG와 위상순서

Directed Acyclic Graph

 

• DAG는 방향 사이클이 없는 방향 그래프
• 예) 작업들의 우선순위

 

위상정렬

• DAG의 노드들을 순서화하는것을 말한다.
• 단, 모든 에지에 대해서 i<j가 되도록

 

 

알고리즘 1

topologicalSort1(G)
{
	for <- 1 to n {
    	진입간선이 없는 임의의 정점 u를 선택한다;
        A[i] <- u;
        정점 u와 u의 진출간선을 모두 제거한다;
    }
    배열 A[1...n]에는 정점들을 위상정렬되어 있다.
}

//수행시간 : O(n+m)
//indegree=0인 노드가 존재하지 않으면?
//indegree 계산?
//어떻게 제거?

 

 

topologicalSort2(G)
{
	for each v C V
    	visited[v] <- NO;
    make an empty linked list R;
    for each v C V => 정점의 순서는 상관없음
    	if(visited[v] = NO) then
        	DFS-TS(v,R);
}

//알고리즘이 끝나면 연결 리스트 R에는 정점들이 위상정렬된 순서로 매달려있다.
//수행시간 : ɵ(n+m)

 

 

 

 

 

 

최단경로

 

최단 경로 : 한 노드에서 다른 노드까지 이동하는데 드는 비용이 최소인 경로를 찾는 문제

 

1. Single - source ( one to all ) 

•  Dijkstra 알고리즘, Bellman-Ford 알고리즘  - 하나의 출발 노드에서 모든 노드까지의 최단 경로를 찾는 문제
•  Dijkstra ( 다익스트라 )다익스트라 알고리즘은 대표적인 음수 가중치가 없다고 가정하는 알고리즘
• -> 음수 사이클이 있으면 돌면 돌수록 작아지기 때문에 최단 경로가 정의되지 않는다.
• ​d[v] : 시작점 s 에서 v 까지 가는데 걸리는 비용 ( distance estimate )
• ㅠ[v] : s 에서 v 까지의 최단 경로상에서의 v 의 직전노드 ( predecessor )
• 처음에는 d[s]=0, d[v] =INF 로 설정하고 알고리즘이 진행됨에 따라 감소해간다. 
• 최종적으로 d[v] 는 = 실제(s,v)  가 된다.
• Relaxation : u -------- v 엣지(u,v) 가 있고 weight 이 2라면    d[u] =5 , d[v] =9 인  상황에 d[v](=9) 는 >= d[u](=5) + w(u,v)(=2) 이기 때문에 갱신되어야한다.

다익스트라

 

• 초기화 d[s]= 0, d[v] = INF, ㅠ[v] = NULL
• 에지들에 대한 반복적인 relaxtion. ( 모든 노드가 집합 S에 포함될때까지 )
• 현재 노드의 인접한 노드들 relaxationn
• distance의 값이 최소인 노드를 선택하고 위의 과정 반복.
• 처음에는 출발 노드의 d[s] = 0 이기 때문에 출발 노드의 엣지들만 relax 한다.

 

2. Single - destination ( all to one ) - 사실상 one to all 이랑 같은 유형

• 모든 노드에서 하나의 목적 노드까지의 최단 경로를 찾는 문제

3. Single - pair ( one to one )  - Dijkstra 알고리즘 으로 해결

• 주어진 한 노드에서 다른 한 목적 노드까지의 최단 경로를 찾는 문제

4. All - pair ( all to all ) - Floyd-warshall 알고리즘.

• 모든 노드에서 모든 노드로 가는 최단 경로를 찾는 문제

 Floyd - Warshall

• Dijkstra 알고리즘과 여타 그래프 문제랑 마찬가지로 가중치 방향 그래프가 입력으로 주어진다.
• 이때, 모든 노드 쌍들간의 최단 경로의 길이를 구하는 문제이다.
• 다익스트라가 가장 적은 비용을 하나씩 선택했다면 플로이드는 '거쳐가는 정점'을 구해가면서 구한다.
• d(k) [ i, j ]  는 중간 노드 집합 { 1,2,3,4 ... k } 에 속한 노드들만 거쳐서 노드 i 에서 j 까지 가는 최단 경로의 길이이다.