2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

2 minute read

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> λΆ€λΆ„μ—μ„œ λ‹€μ‹œ λ“±μž₯ν•œλ‹€! πŸ˜‰

Categories:

Updated: