> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.5-aoe-network.md).

# 4.6 - AOE Network

Activity-on-Edge Network

AOE Network中， $$G=\<V,E>$$為有向圖:

* V(vertex): 代表事件(Event)
* E(edge): 代表工作(Activity)
* Edge上的數值代表工作完成所花時間

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIyJTs-CH6-x1ggM5j0%2F-LIyJWWfzpjjpUG6n_hY%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-03%2013.45.27.jpg?alt=media&amp;token=5b647c9b-1d25-4d5b-a573-bc073177f50d" alt="" data-size="original">&#x20;

* a1, a2均完工，x才會發生
* x發生後，a3, a4才可開工

e.g.

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIyJTs-CH6-x1ggM5j0%2F-LIzMswqJPKPlH6TdAhD%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-03%2018.39.52.jpg?alt=media&amp;token=16a51a64-8553-4dff-81b6-9f154645bfa5" alt="" data-size="original">&#x20;

* 完成此計劃，最快需花多少時間？(1\~8最長的時間＝**Critical Path Length**)

  $$\Rightarrow$$ 事件的最早發生時間

  1. 0
  2. 4+5+4=13
  3. 4+5=9
  4. 4
  5. 13+6=19
  6. 13+5=18
  7. 4+7=11
  8. 18+5=23

  所以需要23個單位時間才有辦法完成整個計畫。

**Critical Path Length: 起點到終點所花最長時間**

* 列出所有Critical Path: (從6到8的皆是Critical Path)

  1. 1→4→3→6→8
  2. 1→4→3→2→6→8

* 哪些工作不可延遲(delay)？

  $$\Rightarrow$$所有Critical Path上的vertex均不可delay

  $$\Rightarrow$$ {3, 4, 5, 7, 8, 12}

* 求各工作最早開工、最晚開工時間？

  $$\Rightarrow$$最晚開工時間從終點最快完成時間往回推，算出事件(vertex)最早發生時間(取最小值)

  <img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIzUIlglVzUJEMwA2JJ%2F-LIzUke4E9sFZMXTq9Mb%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-03%2019.14.15.jpg?alt=media&amp;token=80af622c-d481-4b3f-971e-93461486e39b" alt="" data-size="original">&#x20;