Data Structure
  • 資料結構自學筆記
  • 1 - Stack & Queue
    • 1.1 - Stack
    • 1.2 - Queue
    • 1.3 - Stack and Queue
  • 2 - Tree & Binary Tree
    • 2.1 - Tree
    • 2.2 - Binary Tree
    • 2.3 - Binary Tree Traversal
    • 2.4 - Binary Search Tree
    • 2.5 - Heap
    • 2.6 - Thread Binary Tree
    • 2.7 - Tree and Binary Tree Conversion
    • 2.8 Advanced Trees
      • 2.8.1 - Min-Max Heap
      • 2.8.2 - Deap
      • 2.8.3 - Symmetric Min-Max Heap
      • 2.8.4 - Extended Binary Tree
      • 2.8.5 - AVL Tree
      • 2.8.6 - M-Way Search Tree
      • 2.8.7 - B Tree
      • 2.8.8 - Red-Black Tree
      • 2.8.9 - Optimal Binary Search Tree
      • 2.8.10 - Splay Tree
      • 2.8.11 - Leftest Heap
      • 2.8.12 - Binomial Heap
  • 3 - Search & Sort
    • 3.1 - Searching
    • 3.2 - Elementary Sorting
      • 3.2.1 - Insertion Sort
      • 3.2.2 - Selection Sort
      • 3.2.3 - Bubble Sort
      • 3.2.4 - Shell Sort
    • 3.3 - Sophisticated Sorting
      • 3.3.1 - Quick Sort
      • 3.3.2 - Merge Sort
      • 3.3.3 - Heap Sort
      • 3.3.4 - Radix Sort
      • 3.3.5 - Bucket Sort
      • 3.3.6 - Counting Sort
    • 3.4 - Summary
  • 4 - Graph
    • 4.1 - Intro
    • 4.2 - Graph Traversal
    • 4.3 - Spanning Tree
      • 4.3.1 - Kruskal's algorithm
      • 4.3.2 - Prim's algorithm
      • 4.3.3 - Sollin's algorithm
    • 4.4 - Shortest Path Length
      • 4.4.1 - Dijkstra's algorithm
      • 4.4.2 - Bellman-Ford algorithm
      • 4.4.3 - Floyd-Warshall algorithm
    • 4.5 - AOV Network
    • 4.6 - AOE Network
    • 4.7 - Others
Powered by GitBook
On this page
  1. 4 - Graph

4.6 - AOE Network

Activity-on-Edge Network

Previous4.5 - AOV NetworkNext4.7 - Others

Last updated 6 years ago

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

  • V(vertex): 代表事件(Event)

  • E(edge): 代表工作(Activity)

  • Edge上的數值代表工作完成所花時間

  • a1, a2均完工，x才會發生

  • x發生後，a3, a4才可開工

e.g.

  • 完成此計劃，最快需花多少時間？(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)最早發生時間(取最小值)