Calculation of the routes to the DAG

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

Back to the table of contents
Alterna · Chapter 17 · page 17.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
🔗
Relationship to Chapter 16 (Logic diagrams) and Chapter 17.2
In the logic diagrams, the signal goes from entrances to exits, and it's important to find a way (or all the ways) that the signal can go. In Chapter 17.2, you have learned to describe the graph and count the vertebrates. Now, the next step is: in graphs without cycles (DAG), you can accurately calculate how many paths there are from one point to another. This is necessary to analyse the complexity of the schemes, the calculation of the design options, the planning of the sequence of tasks. DAG is the basis for understanding how assembly projects (make, npm) work, how cryptation without blockage (IOTA, Nano) is done, how neural computations are planned.
📊
Examples of DAG
a.c
b.c
lib.o
app
main.o
makefile
Project compilation
Makefile, package.json
Which files should be collected before the others.
Tx1
Tx2
Tx3
Tx4
Tx5
IOTA DAG
IOTA Blocking
DAG instead of the block chain
Instead of a linear chain, it's a graph of transactions, faster and more scalable.
x
w₁
w₂
σ
f
ŷ
Neuroste
Computation graph of neuronets
Operations and operations
The layers of neuronets are the vertices, and the dependencies are the ribs.
U.S.A.
Walls
Commune
roof
windows
home
Network schedule of construction
What work should end?
A critical path, time analysis, DAG helps plan.
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
Calculation of the routes to the DAG
What is DAG?
DAG
(Directed Acyclic Graph) is a focused graph without cycles. This means that the ribs can be reached from any top in only one direction, and it is not possible to encapsulate.
Why count the tracks?
DAG information technology is used for:
Project planning (web schedules)
Calculation of how to accomplish the tasks
Macefile Dependence Analysis
Network routes
Dynamic programming formula
Let
dp[v]
— Number of tracks from the top
s
Up to the top
v
.
Base:
dp[s] = 1
— A path from one top to itself (zero length)
Transition:
dp[v] = Σ
u → v
dp[u]
— The sum of the paths of all the predecessors
Order:
Topological sorting
- First the ancestors, the descendants.
Topological sorting
Algorithm: Find the vertices from
in-degree = 0
, add in line, remove their ribs, repeat. The result is the order in which all the ancestors of any vertice are already processed.
Complexity
Time:
O(V + E)
- one passage through all the tops and ribs.
O(V)
For storage dp.
📊
Simulator: calculation of routes in DAG
Start
Finish
Press "Shag" for stepwork or "Animation" for auto-reproduction.
The complete execution log:
03
Dakestra algorithm
Definition
Dakestra algorithm
Finds a quick path from one top to all the others in a weighted graph without negative ribs.
Distance to starter = 0, to rest = .
Select the top with a minimum distance (not visited).
For each rib: if the path to the neighbor is through the current shorter, update.
Repeat until all the tops are visited.
Where used
GPS navigation, network routeting, character-tracking, robotics.
🗺
Dakestra Visualizer
Algorithm diagram:
1. dist[s]=0, остальным =∞
2. Повторять:
a) выбрать необработанную вершину с мин dist
b) пометить её обработанной
c) для каждого ребра u→v с весом w:
если dist[u]+w < dist[v]:
dist[v] = dist[u]+w
prev[v] = u
3. Повторять пока очередь не пуста
Start
04
Mini test
📝
DAG and ways — 5 out of 50
Level:
Newcomer
0
/
50
XP
⬡
0
Question 1 out of 5
♪ Series:
0