DAG & Topological Sort
2020-1νκΈ°, λνμμ βμκ³ λ¦¬μ¦β μμ μ λ£κ³ 곡λΆν λ°λ₯Ό μ 리ν κΈμ λλ€. μ§μ μ μΈμ λ νμμ λλ€ :) μ 체 ν¬μ€νΈλ Algorithm ν¬μ€νΈμμ νμΈνμ€ μ μμ΅λλ€.
<DAG; Directed Acyclic Graph>λ cycleμ΄ μ‘΄μ¬νμ§ μλ directed graphλ₯Ό λ§νλ€.

μ΄λ, λͺ¨λ DAGμ λ Έλλ <topological ordering>λ₯Ό κ°μ§κΈ° λλ¬Έμ, μ°λ¦¬λ DAGλ₯Ό <topological sort>λ‘ linearization ν μ μλ€!!
μ΄κ²μ DAGκ° κ°λ μ±μ§ λλ¬ΈμΈλ°, βEvery DAG has at least one vertex with no incoming edge.βμ΄κΈ° λλ¬Έμ΄λ€! μ΄ μ±μ§μ λ°λΌ, <topological sort>λ DAGμ μ‘΄μ¬νλ vertex with no incoming edgeλ₯Ό νλμ© μ κ±°ν΄κ°λ©΄μ, DAGλ₯Ό linearization νλ€ π€©
μμμ μ μν DAGμ λν΄ vertex with no incoming edgesλ₯Ό λ°λ³΅μ μΌλ‘ μ κ±°νμ¬ topological sortλ₯Ό μννλ©΄, κ·Έ κ²°κ³Όλ μλμ κ°λ€.

DAGκ³Ό topological ordering μ¬μ΄μ κ΄κ³λ₯Ό κΈ°μ νλ©΄ μλμ κ°λ€.
A directed graph is a DAG iff it has a topological ordering.
μ΄λ κ² DAGλ₯Ό topological orderλ‘ linearization νλ€λ©΄, μ°λ¦¬λ DAG μμμμ shortest pathλ₯Ό μ½κ² ꡬν μ μλ€.
Linearize $G$
for each $u \in V$ in linearized order
ββfor all edges $(u, v) \in E$
ββββ$\texttt{update}(u, v)$
ββend for
end for
μ°Έκ³ λ‘ μ£Όμ΄μ§ κ·Έλνκ° DAGλΌλ©΄, negative edgeκ° μμ΄λ μμ κ°μ λ°©μμΌλ‘ μΆ©λΆν shortest pathλ₯Ό ꡬν μ μλ€!! (DAGλ cycleμ΄ μκΈ° λλ¬Έμ, negative cycleμ λν κ±±μ μ΄ μλ€! π)
μ¬κΈ°κΉμ§κ° μ κ· μμ μμ λ€λ£¬ <Graph Algorithm>μ λν λ΄μ©μ΄λ€. κ·Έλν μ΄λ‘ μ PSμ κΈ°λ³Έμ΄κΈ° λλ¬Έμ μ΄κ³³μμ λ€λ£¬ λͺ¨λ λ΄μ©μ μμ ν μ΄ν΄νκ³ μΈμ λ μ§ μΈ μ μλλ‘ νλκ² μ€μν κ² κ°λ€. βμκ³ λ¦¬μ¦β κ³Όλͺ©μ μ κ· μμ μμ λ€λ£¨μ§λ μμμ§λ§, βμΈκ³ μ§λ₯β κ³Όλͺ©μμλ λ€λ€λ heuristic path finding κΈ°λ²μΈ <A* Algorithm>λ μΆνμ λ€λ€λ³΄λλ‘ νκ² λ€.
κ·Έλνμ λν λ΄μ©μ λμ€μ <Network Flow> λΆλΆμμ λ€μ λ±μ₯νλ€! π