【Data Structure】why Is the Earliest Occurrence Time of an Event in the Critical Path the Longest Path Length From the Source Point to the Vertex

Multi-version JDK switching solution
【Data Structure】Why is the earliest occurrence time of an event in the critical path the longest path length from the source point to the vertex?

Before thinking about this, let's first understand, in the critical path, what is the difference between start and happen?
start and happen
"Occurrence" is for events, ie vertices in the graph. The event represented by this vertex occurs only when the activities corresponding to all directed edges pointing to this vertex have ended.
For example, an event C, which is only pointed to by two edges a and b, occurs only when both activities a and b are completed.
"Start" is for activities, which are edges in the graph. Activities corresponding to all edges originating from a vertex can begin only after the event represented by that vertex occurs.
Earliest time of occurrence
At first I was also very confused, why does the longest path length determine the earliest occurrence time? Shouldn't it be that the sooner you want to happen , the shorter the path?
  Later, I realized that the shortest path and the critical path are not the same thing at all. Finding the shortest path is to find the shortest path as possible to ensure the minimum path length. You only need to find the shortest path. However, in the critical path, a vertex has multiple preconditions. Only when the premise paths are completed can the event of the vertex occur. Then only the longest path is completed, and the rest of the short paths are guaranteed to have been completed. The event just happened.

As we said earlier, occurrence is for events. For an event to occur, the activities that point to it must first be completed. An event C is pointed to by two activities a and b. The time consumption of activity a is 3, and the time consumption of activity b is 5. So look at the picture below, how long does it take from the beginning to the occurrence of event C?

It is the maximum path length of 5, because the premise of event C must be that two activities a and b are completed (the activities can be performed at the same time), and event C will only occur when b is completed. That's why the longest path length is taken.
latest time

The definition of the latest occurrence time is as follows: on the premise of not delaying the completion of the entire project, to ensure that the subsequent event j can occur at its latest occurrence time vl (j), the latest time that the event must occur.

First of all, we need to know that the latest occurrence time of the sink is its earliest occurrence time (it can be understood that the earliest occurrence time of the sink is the construction period), and the process of seeking VL is pushed back from the sink.
Second, why is there a late occurrence time? This is because in a project, there is usually a certain path that takes longer than other paths, so events that take a short time do not need to occur too early, that is, there is a buffer time.
Let's take a look at the following example and see what is the latest time to happen?

Looking at the graph, I wrote it's earliest occurrence above the vertex, D is the sink, and 110 is its earliest occurrence (and also latest).

At this point, we can understand it this way, if the project must be completed in 110 days, when will the event A happen at the latest?
We can subtract the time of activity a from 110 to get 105, which means that the event A can happen on the 105th day at the latest (the activity a must be started immediately once it happens, otherwise the entire duration will be postponed), and the activity pointing to A can be started on the 105th day at the latest. 100 days to start.
And event A can happen on the 5th day at the earliest (here it makes sense at the earliest), and it can be completed on the 5th day at the earliest, but it can be postponed to the 105th day, and there is a 100-day difference in the middle.

Data Structure.In the same way, the latest time for event B to occur is the 10th day, and it cannot be delayed for a moment.

Data Structure.At this time, go back and look at the definition of the latest occurrence time, it should be understandable.
time margin
Data Structure. difference between the latest start time of the activity and the earliest start time, which represents how long the activity can be delayed. If the time margin of an activity is 0, it means that the activity cannot be delayed. It is called a key activity and must be completed immediately, otherwise the entire duration will be delayed.
critical path is the connection of all edges with a time margin of 0 .

If the time margin d is required, the earliest start time e and the latest start time l of the activity must be obtained first, and the earliest occurrence time ve and the latest occurrence time vl of the event must be obtained first if e and l are required . So the steps to do the question come out, and finally let's do a question and try it!

Data Structure.The answer is as follows:

The final critical path is (v1, v3, v4, v6)

Data Structure.A few final notes:

1. All activities on the critical path are key activities, which are the key factors in determining the entire project, so the entire construction period can be shortened by speeding up key activities. But it cannot be shortened arbitrarily, because once shortened to a certain extent, the key activity may become a non-critical activity
2. The critical path in the network is not unique. For a network with several critical paths, only speeding up the activities on one of the critical paths cannot shorten the construction period. Shorter durations can only be achieved by expediting critical activities that exist on all critical paths.

phone Contact Us