Calculation of the routes to the DAG

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

Back to the table of contents
Alterna · Chapter 16 · page 16.3
Calculation of the routes to the DAG
Topological sorting + dynamic programming.
DAG (DAG)
The main property is that you can sort the vertebrates from the top. This is the basis for the O(V+E) path count algorithm.
GEF
PIF
OGE No. 9
EGE No. 1
01
DAG and its properties
Definition
DAG (Directed Accelic Graph)
- a focused graph with no cycles.
Topological sorting
is a linear top alignment in which each rib u of v goes "first" (u before v).
There is then and only when the Count is DAG.
Where you meet
Project compilation:
Make files, package.json is the assembly order.
Task planner:
What are the challenges that depend on others?
Git:
Commite history (DAG, not chain).
Neironeti:
Computer chart of operations.
Cryptovalyts:
DAG, not the IOTA chain, Nano.
Example of DAG (6 vertices)
Ribs: 1 and 2, 1 and 3, 2 and 4, 2 and 5, 4 and 6 and 6.
Topsort: 1, 2, 3, 4, 5, 6 (one option).
02
The path count algorithm
Dynamic programming method
Let
dp[v]
is the number of tracks from the starting point s to v.
Base:
dp[s] = 1 (way from one vertex to itself).
Transition:
dp[v] = dp [u] for all ribs (u \v).
Rounding order:
Topological sorting (first of all, ancestors, descendants).
Complexity:
O(V + E).
📊
Simulator: calculation of routes in DAG
Start
Finish
03
Mini test
📝
6 questions on DAG