Minimum spanning tree, shortest path, topology sorting, critical path

One 、 Minimum spanning tree

PLIM algorithm and Kruskal algorithm are two applications MST Properties of the algorithm for constructing the minimum spanning tree .

1、 The prim algorithm （“ Add points ”）

2、 Kruskal algorithm

Two 、 Shortest path

1、 Dijkstra algorithm

（ Distance from a source point to the remaining vertices ）
The time complexity is O(n^2)

2、 Freudian algorithm

（ The shortest path between each pair of vertices ）
The time complexity is O(n^3)

3、 ... and 、 A topological sort

1、AOV- network
Use vertices to represent activities , A graph in which the priority relationship between activities is represented by an arc is called a network in which vertices represent activities , abbreviation AOV- network .
Be careful ：
（1） stay AOV- In the net , There should be no directed ring ;
（2） The way to check whether there is a directed ring is to sort the vertices of a directed graph ;
2、 A topological sort
Concept ：
The so-called topological sorting is to sort AOV- All vertices in the net are arranged in a linear sequence , The sequence satisfies ： If in AOV- There are vertices in the net Vi To the top Vj There is only one way , Then the vertices in the linear sequence Vi Must be at the vertex Vj Before .
The process ：
（1） Select a vertex without precursor in a directed graph and output it ;
（2） Delete the vertex and all arcs ending in it from the graph ;
（3） repeat （1） and （2）, Until there is no Vertex without precursor ;
（4） If the number of output vertices is less than the number of vertices in the directed graph , There is a ring in the graph , Otherwise, the output vertex sequence is a topological sequence ;

Four 、 critical path

1、AOE- network
AOE- A net is a weighted directed acyclic graph , among , A vertex represents an event , Arcs represent activities , Right means the duration of the activity . Usually ,AOE- The net can be used to estimate the completion time of the project .
2、 Several definitions ：
（1） Source point ： There is only one point with zero penetration in the network ;
（2） Confluence ： There is only one point in the net where the outgoing degree is zero ;
（3） Weighted path length ： The sum of the weights on the arcs of a path ;
（4） critical path ： Find a path with the longest weighted path length from the source point to the sink point ;
3、 The process of solving critical path
（1） Sort the vertices in the graph , In the sorting process, the earliest occurrence time of each event is calculated according to the topological sequence ve(i);
（2） Calculate the latest occurrence time of each event according to the inverse topological sequence vl(i);
（3） Find out each activity ai The earliest start time of e(i);
（4） Find out each activity ai Latest start time of l(i);
（5） find e(i)=l(i) The activities of ai, This is the key activity . Each path from the source point to the sink point formed by key activities is a key path （ There may be more than one critical path ）;
4、 How to find a few times