AlgoVerse

Critical path (AOE network)

In an activity network, compute each event's earliest and latest time and find the activities that cannot be delayed at all.

In an AOE network (activity on edge), each edge is an activity with a duration and each node is an event ("all incoming activities are done"). The questions:

Read the full explanation ↓
Input:
V=9 · E=11 · src=0PDF export

Nine events and eleven activities; the project takes 18, and there are two critical paths from 0 to 8.

  1. def critical_path(graph, src):
  2. # The project starts at time 0; src is ignored.
  3. seen = set()
  4. order = []
  5. for s in graph:
  6. if s not in seen:
  7. topo(graph, s, seen, order)
  8. order.reverse()
  9. early = {v: 0 for v in graph}
  10. for u in order:
  11. for v, w in graph[u]:
  12. if early[u] + w > early[v]:
  13. early[v] = early[u] + w
  14. finish = max(early.values())
  15. late = {v: finish for v in graph}
  16. for u in reversed(order):
  17. for v, w in graph[u]:
  18. if late[v] - w < late[u]:
  19. late[u] = late[v] - w
  20. critical = []
  21. for u in graph:
  22. for v, w in graph[u]:
  23. if early[u] + w == late[v]:
  24. critical.append((u, v, w))
  25. return finish, critical
  28. def topo(graph, u, seen, order):
  29. seen.add(u)
  30. for v, _ in graph[u]:
  31. if v not in seen:
  32. topo(graph, v, seen, order)
  33. order.append(u)

Invariant: early[v] is the soonest time all activities into v are done, and late[v] is the latest v may happen without delaying the project.

Start

64511297424012345678
  • Current node (u)
  • Shortest-path tree so far
  • Edge being checked

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

src'0'

Orange = changed in this step

graph dict
  • '0': [('1', 6), ('2', 4), ('3', 5)]
  • '1': [('4', 1)]
  • '2': [('4', 1)]
  • '3': [('5', 2)]
  • '4': [('6', 9), ('7', 7)]
  • '5': [('7', 4)]
  • '6': [('8', 2)]
  • '7': [('8', 4)]
  • '8': []

Call stack

  1. critical_path()line 1
Step 1 of 242
Black = length · Orange = key steptopo_ready: 0/1 · forward: 0/11 · later: 0/10 · length: 0/1 · backward: 0/11 · sooner: 0/8 · slack: 0/11 · critical: 0/6

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • forward
    • backward
    • current input (n=9)
    0204060481216202428n = number of nodesforwardbackward
    Show as a table
    nforwardbackward
    45.25.2
    813.813.8
    1220.820.8
    162828
    2035.435.4
    2437.237.2
    2847.247.2
    Explanation

    The idea

    In an AOE network (activity on edge), each edge is an activity with a duration and each node is an event ("all incoming activities are done"). The questions:

    • How long does the project take at least?
    • Which activities are critical, meaning any delay to them delays the whole project?

    Two passes

    1. Forward (in topological order): early[v] = max(early[u] + w) over incoming edges. The largest early is the project's length. This is the longest path.
    2. Backward (in reverse order): late[u] = min(late[v] − w) over outgoing edges.

    An activity u → v of duration w has no slack and is critical if early[u] + w = late[v]. The critical paths are made of critical edges.

    What to watch in the trace

    • The number by each node is its early time; late is in the memory panel.
    • The coloured edges are the critical activities.