1, Critical path algorithm
Critical path algorithm is to find out several key activities when the project can be completed, so as to achieve the effect of completing the project earlier.
2, Algorithm analysis
In this algorithm, we need to use the variables etv, ltv, ete and lte, as well as the algorithm to ensure the completion of the project, that is, the topological sorting algorithm
In this algorithm, we regard vertices as events, edge weights as activity duration, and edges as activities
Explain the meaning of these variables, etv and ltv (i.e. the earliest start time and the latest start time of the event)
ete, lte (i.e. the earliest start time and the latest start time of the activity)
3, Algorithm steps
1. Use topological sorting to find out whether the critical path can be queried
2. In the process of topological sorting, the earliest start time of events is calculated
3. The stack is used to store the topology sequence, and then the latest start time of events is pushed from the top of the stack
4. Use ete and lte to judge whether this activity is a key activity
5.ete is equal to the earliest start time of this event (why? Because if you want this event to happen, you must wait for all the previous things to happen, so it is the solution step of the earliest start time)
6.lte is equal to the latest start time of the next event minus the duration (why? Because the latest start time of the next event represents whether the subsequent events can be carried out normally, that is, whether the subsequent activities can be carried out. Similarly, the latest start time of the activity should also be the latest start time duration of the next event)
4, Code implementation
1 #include "bits/stdc++.h" 2 using namespace std; 3 int etv[110],ltv[110];//etv Is the earliest start of the event, ltv Is the latest start event of the event 4 int indegree[110];//Record the penetration of a vertex 5 int u[110],v[110],w[110];//Establish adjacency table 6 int first[110],outnext[110]; 7 stack <int> Topo; 8 int n,m; 9 void TopologicalSort()//Sort topology 10 { 11 int cnt = 0; 12 queue <int> ans; 13 for(int i = 1;i <= n;i++) 14 if(!indegree[i])//Put the points with a penetration of 0 into the queue 15 ans.push(i); 16 while(!ans.empty()){ 17 int v1 = ans.front(); 18 ans.pop(); 19 Topo.push(v1);//Put the topologically sorted sequence into the stack to pave the way for solving the latest event start event later 20 cnt++; 21 int k = first[v1];//Traverse all his edges 22 while(k != -1){ 23 if(!(--indegree[u[k]]))//Points with statistical penetration of 0 are added to the topological sequence 24 ans.push(u[k]); 25 etv[u[k]] = max(etv[u[k]],etv[v1] + w[k]);//Why is the maximum value required to solve the earliest start time of an event? Because you need to ensure that all the previous events have ended, you can only count the longest time in the first few 26 k = outnext[k]; 27 } 28 } 29 if(cnt < n)//Determine whether it is a topological sequence 30 cout << "Fail" << endl; 31 else 32 cout << "Successful!" << endl; 33 } 34 void CriticalPathMethod() 35 { 36 TopologicalSort();//Sort topology 37 for(int i = 1;i <= n;i++)//because ltv Is to find the minimum value, then the maximum in this array must also be etv The largest in the, which will not affect ltv Solution of the value of 38 ltv[i] = etv[n]; 39 while(!Topo.empty()){//Solve from the sink point (end point) to the source point (starting point) ltv((latest start time) 40 int v1 = Topo.top(); 41 Topo.pop(); 42 int k = first[v1]; 43 while(k != -1){ 44 ltv[v[k]] = min(ltv[v[k]],ltv[u[k]] - w[k]);//Why min And? Because you have to make the later activities can be carried out according to the normal time, you can't use the maximum, otherwise the later projects may be affected 45 k = outnext[k]; 46 } 47 } 48 int ete,lte;//ete Is the earliest start time of the activity, lte Is the latest start time of the activity. (here, activities refer to edges and events refer to vertices) 49 for(int i = 1;i <= n;i++){ 50 int k = first[i]; 51 while(k != -1){ 52 ete = etv[i];//The earliest start time of the activity is the longest path before this, so it is the earliest start time of the event 53 lte = ltv[u[k]] - w[k];//The latest start time of the activity is the latest start time without delaying the construction period, that is, the latest occurrence time of the event-This duration (i.e. edge weight) 54 if(lte == ete)//When the earliest activity start time is equal to the latest activity start time, this activity is a key activity, and the complete set of key activities is a key path, and there may be more than one key path 55 cout << "(" << i << ',' << u[k] << ')' << ":weight" << w[k] << endl; 56 k = outnext[k]; 57 } 58 } 59 } 60 int main() 61 { 62 cin >> n >> m; 63 for(int i = 1;i <= n;i++) 64 first[i] = -1; 65 for(int i = 1;i <= m;i++){ 66 cin >> v[i] >> u[i] >> w[i]; 67 indegree[u[i]]++;//Penetration+1 68 outnext[i] = first[v[i]]; 69 first[v[i]] = i; 70 } 71 CriticalPathMethod(); 72 return 0; 73 }
V. test data
test case1
6 8
1 2 3
1 3 2
2 5 3
2 4 2
3 6 3
4 6 2
5 6 1
3 4 4
answer1
test case2:
10 13
1 2 3
1 3 4
2 4 5
3 4 8
2 5 6
3 6 7
4 5 3
5 8 4
6 8 6
8 9 5
5 7 9
7 10 2
9 10 3
answer2