Calculation of the routes to the DAG

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 24 · page 24.3
Calculation of the routes to the DAG
Topological sorting (Cana) + dynamic programming + critical path.
For DAS, the number of tracks is counted as O(V+E) — topologically sort the vertices, then the DP from start.
of the critical path
In project management.
GEF
PIF
EGE No. 1
He's got a little bit of depth.
01
Topological sorting (Kan algoritm)
Topological sorting is a linearly structured top placement of Directed Acyclic Graph (DAG) so that for each of the u'v ribs the v's is the top of the v. It is the foundation for the DP on the graphs.
Kang algorithm: stepwise
Calculate in-degree
each vertex is the number of ribs that enter it.
Initiate the line
- put all the vertebrates with in-degree = 0.
Remove u
from the line, add to the end of the result (top order).
Reduce In-Degree
For each neighbor v of the rib u.v. If in-degree[v] becomes 0, add v in line.
Repeat
Steps 3-4 until the line is empty.
Verification:
If, as a result of the fewer vertices, the graph contains a cycle (the topsort is not possible) than the graph.
Complexity
O(V + E)
- each vertex and each rib are treated exactly once. The implementation uses a line (_FIFO_), but let's also have a stack.
Example in the box of 7 vertices
Step 1:
in-degree: A=0, B=1, C=1, D=2, E=2, F=1, G=4
Step 2:
Line: [A]
Step 3:
Extract A is the result: [A]
Step 4:
B, C: in-degree B = 0, C = 0 : [B, C]
Step 3:
Extract B × result: [A, B]
Step 4:
B→D, B→E: in-degree D=1, E=1
Step 3:
Extract C × result: [A, B, C]
Step 4:
C.E., C.F.: in-degree E=0, F=0 . line: [E, F]
…
continue to G
Outcome:
A ♪ B * C * E * F * D * G (one option)
Why do you need a topsort?
It guarantees that all the ancestors of each vertex are already processed when they bypass the vertices in the order they have been obtained, which is exactly what is needed for the correct DP.
02
DP for track calculation
Objective:
DAG and two vertices s and e. How many different Directed Paths exist from s to e?
Formula
dp[v] = dp [u] for all ribs u \v
Base:
dp[s] = 1 (one "zero length path" from s to s). All other dp values are initialized by zero.
Rounding order:
The tops in topological order (the result of the Kan algorithm).
Pseudocode
topsort
← Kahn(G)
dp
[s] ← 1
for
v
in
topsort:
for
each u → v
in
edges:
dp[v] ← dp[v] + dp[u]
return
dp[e]
Complexity
O(V + E) is a topsort + one passage through the ribs.
Extension: The longest path
For the critical path task, the formula is modified:
dist[v] = max(dist[u] + w(u,v)) for all u \v
Here w(u,v) is the weight (longitude) of the rib.
CPM (Critical Path Method)
.
Step-by-step calculation of the tracks A ± G
Count: A.B., A.C., B.D., C.E., K.F., D.G., E.G, F.G
Topsort: A B C E F D G
Initialization:
dp[A]=1, the rest dp=0
Step A:
rib A ± B (dp[B]+=dp [A]=1), A ± C (dps[C]+ =1)
→ dp: A=1, B=1, C=1, D=0, E=0, F=0, G=0
Step B:
bbbb (dp[D]+=dp [B]=1), bp[E]+ =1)
→ dp: A=1, B=1, C=1, D=1, E=1, F=0, G=0
Step C:
:: rib C:E (dp[E]+=dp [C] = 1 : dp [E] = 2), C:F (dpp[F]+ =1)
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=0
Step E:
== sync, corrected by elderman == @elder_man
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=2
Step D:
== sync, corrected by elderman == @elder_man
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=3
Step F:
== sync, corrected by elderman == @elder_man
Total:
4 tracks
from A to G!
Check in the simulation: pick the start=A, finish=G, press Count.
def count_paths_dag(n, edges, start, end):
# edges = [(u, v), ...]
adj = [[] for _ in range(n)]
indeg = [0]*n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
# Кана: топологическая сортировка
q = [i for i in range(n) if indeg[i] == 0]
topo = []
while q:
v = q.pop(0)
topo.append(v)
for u in adj[v]:
indeg[u] -= 1
if indeg[u] == 0:
q.append(u)
# DP
dp = [0]*n
dp[start] = 1
for v in topo:
for u in adj[v]:
dp[u] += dp[v]
return dp[end]
# Пример:
edges = [(0,1),(0,2),(1,3),(1,4),(2,4),(2,5),(3,6),(4,6),(5,6)]
print(count_paths_dag(7, edges, 0, 6)) # 4
🔢
DP: Tracking — Animation
03
Critical Path (CPM)
Critical Path Method (Critical Path Method, CPM)
Each task is a weight rib (time of execution), each peak is a Milestone (event).
What is a critical path?
A Critical Way Is
The longest way
It determines the minimum possible time for completion of the project: if any mission is delayed, the entire project is delayed.
CPM application
Construction:
The foundation of the walls is the roof of the roof and the critical path is the longest area.
Development of software:
Analytician ♪ design ♪ coding ♪ testing ♪
Production:
Procurement of materials for the collection of materials
Logistics:
The route with maximum delay determines the total time of delivery.
Algoritm
Find a topological order of the tops (Kan's algoritm).
Direct passage: dist[v] = max(dist[u] + w(u,v)) for all incoming ribs u\v.
Reverse passage (optional): for each rib on the critical path . ./ ., time coincides.
Critical path = multiple ribs where dist[v] = dist[u] + w(u,v) and achievable is maximized.
Important
The critical path is not that there can be more than one. All tasks on the critical path have
zero reserve
(float = 0): they cannot be postponed without an extension of the overall period.
Example
Project objectives:
A.B. (3 days), A.C. (2 days), B.D. (4 days), C.E. (2 day), D.G. (1 day), E.G (2 days) and F.G (1 day)
Critical route:
A → B → D → G = 3+4+1 =
8 days
(A'B'E'G's path = 3+2+2=7 days is not critical)
def cpm_critical_path(tasks):
# tasks = [{id, from, to, dur}, ...]
nodes = sorted(set(sum([[t['from'], t['to']] for t in tasks], [])))
adj = {n: [] for n in nodes}
indeg = {n: 0 for n in nodes}
for t in tasks:
adj[t['from']].append((t['to'], t['dur']))
indeg[t['to']] += 1
# Forward pass
early = {n: 0 for n in nodes}
q = [n for n in nodes if indeg[n] == 0]
order = []
while q:
v = q.pop(0)
order.append(v)
for to, w in adj[v]:
early[to] = max(early[to], early[v] + w)
indeg[to] -= 1
if indeg[to] == 0: q.append(to)
project_dur = early[order[-1]]
# Backward pass
late = {n: project_dur for n in nodes}
for v in reversed(order):
for to, w in adj[v]:
late[v] = min(late[v], late[to] - w)
# Float & critical path
critical = [t['id'] for t in tasks if late[t['from']] - early[t['from']] == 0]
return critical, project_dur
tasks = [
{'id':'A','from':'S','to':'A','dur':3},
{'id':'B','from':'S','to':'B','dur':2},
{'id':'C','from':'A','to':'C','dur':4},
{'id':'D','from':'A','to':'D','dur':2},
{'id':'E','from':'B','to':'D','dur':3},
{'id':'F','from':'C','to':'F','dur':1},
{'id':'G','from':'D','to':'G','dur':2},
{'id':'H','from':'E','to':'G','dur':1},
{'id':'I','from':'F','to':'I','dur':3},
{'id':'J','from':'G','to':'J','dur':2},
]
path, dur = cpm_critical_path(tasks)
print(f"Критический путь: {' → '.join(path)} ({dur} дней)")
⚡
CPM: step-by-step critical path
04
Simulator: calculation of tracks + critical path
📊
DP: Paths and the Critical Path
Start
Finish
05
Interactive: CPM - Project Planner
Synthetic the project: set the duration of the task and learn the critical path + the reserve of each task.
📋
C