[Algorithms] Shortest Path in DAG | 사이클이 없는 방향 그래프의 최단 경로

Shortest Path in DAG

사이클이 없는 방향 그래프의 최단 경로

* DAG (Directed Acyclic Graph)
- "사이클이 없는 방향 그래프"의 약자이다.

- DAG에서는 모든 정점을 한 줄로 늘어놓으면,
  뒤에 위치한 정점부터 앞에 위치한 정점으로 가는 간선은 존재하지 않도록 하는(=역방향으로 가지 못하는)
  정점들의 순열이 존재한다.
- DAG에서 이러한 순열은 위상 정렬을 통해 얻을 수 있다.
- DAG의 경우, 간선들의 가중치의 부호를 모두 바꾸어 수행하면 최장 경로까지도 계산해낼 수 있다.
  (반면, 벨만-포드, 다익스트라 알고리즘에서는 최장 경로를 계산해낼 수 없다.)
- DAG를 넘어서, 일반적인 그래프에서 최장 경로를 구하는 문제는 NP-Complete에 해당되는 문제이다.

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

* Topological Sorting (위상 정렬) (URL)

[Algorithm] Topological Sorting | 위상 정렬

---

 

Mechanism (원리)

---

Implementation (구현)

* GitHub (URL)

* Pserudo Code

DAG_shortest_path(G, r)
// G = (V, E) : Given Graph
// r : Starting Vertex
// L(u) : Set for Adjacency Vertices of Vertex 'u'
// d[v] : Minimum Cost to connect with Vertex 'v' and Spanning Tree
{
    for(u ∈ V)
        d[u] = ∞;
    d[r] = 0;
    
    topological_sorting(G);
    
    for(u ∈ V) // on topological order
        for(v ∈ L(u))
            if(d[u] + w(u, v) < d[v]) {
                d[v] = d[u] + w(u, v);
                prev[v] = u;
            }
}

---

Performance (성능)

Time Complexity : \(\Theta(|V|+|E|)\)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)