Tip:
Highlight text to annotate it
X
- WELCOME TO THE FIRST LESSON ON THE BACKFLOW ALGORITHM
AND THE CRITICAL PATH ALGORITHM, VERSION TWO.
IN THIS LESSON WE WILL CREATE A PRIORITY LIST
USING THE BACKFLOW ALGORITHM.
IN PART TWO WE'LL CREATE A PRIORITY LIST AND A SCHEDULE.
IN OUR LAST LESSON WE USE
A CRITICAL PATH ALGORITHM GIVEN BELOW.
NOTICE HOW THIS IS VERSION ONE OF THE CRITICAL PATH ALGORITHM
TO CREATE A PRIORITY LIST AND THEN A SCHEDULE.
YOU COULD IMAGINE THAT SEARCHING FOR THE CRITICAL PATH
EVERY TIME YOU REMOVE A TASK FROM THE DIAGRAPH
WOULD GET REALLY TIME CONSUMING, ESPECIALLY FOR A LARGE DIAGRAPH.
IN PRACTICE, THE CRITICAL PATH ALGORITHM IS IMPLEMENTED
BY FIRST WORKING FROM THE END BACKWARDS.
THIS IS CALLED THE BACKFLOW ALGORITHM.
AND HERE ARE THE STEPS FOR THE BACKFLOW ALGORITHM.
STEP ONE, WE INTRODUCE AN END VERTEX AND ASSIGN IT
A TIME OF ZERO SHOWN IN BRACKETS.
STEP TWO, WE MOVE BACKWARDS TO EVERY VERTEX
THAT HAS AN ARROW TO THE END AND ASSIGN IT A CRITICAL TIME.
STEP THREE, FROM EACH OF THESE VERTICES,
MOVE BACKWARDS AND ASSIGN THOSE VERTICES CRITICAL TIMES.
NOTICE THAT THE CRITICAL TIME FOR THE EARLIER VERTEX
WILL BE THE TASK TIME PLUS THE CRITICAL TIME
FOR THE LATER VERTEX.
CONSIDER THIS SEGMENT OF THE DIAGRAPH.
IN THIS CASE, TASK TWO HAS ALREADY BEEN DETERMINED
TO HAVE A CRITICAL TIME OF TEN.
LET'S CALL IT TEN HOURS.
THEN TASK 1 WILL HAVE A CRITICAL TIME OF 5 + 10 = 15 HOURS.
WE TAKE THE 10 AND THE TIME IT TAKES TO COMPLETE TASK 1
TO GET THE NEW CRITICAL TIME OF 15 HOURS.
BUT IT'S NOT ALWAYS QUITE THIS STRAIGHTFORWARD.
IF YOU HAVE ALREADY ASSIGNED A CRITICAL TIME TO A VERTEX,
REPLACE IT ONLY IF THE NEW TIME IS LARGER.
AS AN EXAMPLE, IN THE DIAGRAPH BELOW,
TASK 1 SHOULD BE LABELED WITH A CRITICAL TIME OF 16 HOURS
SINCE IT IS THE LONGER OF THE 5 + 10 AND THE 5 + 11.
WE ALWAYS TAKE THE LONGER CRITICAL TIME.
STEP FOUR, REPEAT UNTIL ALL VERTICES
ARE LABELED WITH THEIR CRITICAL TIMES.
ONCE THE BACKFLOW ALGORITHM IS COMPLETE,
YOU CAN EASILY CREATE THE CRITICAL PATH PRIORITY LIST
BY USING THE CRITICAL TIMES JUST FOUND,
WHICH LEADS US TO VERSION TWO OF THE CRITICAL PATH ALGORITHM.
STEP ONE, WE APPLY THE BACKFLOW ALGORITHM TO THE DIAGRAPH.
STEP TWO, CREATE THE PRIORITY LIST BY LISTING THE TASKS
IN ORDER FROM LONGEST CRITICAL TIME TO SHORTEST CRITICAL TIME.
LET'S TAKE A LOOK AT OUR EXAMPLE.
FIRST STEP, LABEL THE END WITH A CRITICAL TIME OF ZERO.
LET'S CALL IT ZERO HOURS.
NOTICE TASK NINE, 10 AND FOUR LEAD TO THE END.
AND THEREFORE, TASK NINE WOULD HAVE A CRITICAL TIME
OF NINE HOURS.
TASK TEN WOULD HAVE A CRITICAL TIME OF TWO HOURS.
AND TASK FOUR, WOULD HAVE A CRITICAL TIME OF THREE HOURS.
NOW WORKING OUR WAY BACKWARDS, LETS TAKE A LOOK AT TASK FIVE.
IF WE USE THIS PATH HERE,
NOTICE HOW THE CRITICAL TIME WOULD BE 9 + 8 = 17 HOURS.
IF WE USE THIS PATH, NOTICE HOW THE CRITICAL TIME
WOULD BE 2 + 8 = 10 HOURS.
SINCE 10 IS