- 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 <17, WE KEEP THE HIGHER VALUE OF 17.
LOOKING AT TASK 8, USING THIS PATH,
THE CRITICAL TIME WOULD BE 2 + 7 = 9 HOURS.
LOOKING AT TASK 7, THE CRITICAL TIME WOULD BE 9 + 6 = 15 HOURS.
LOOKING AT TASK THREE,
THE CRITICAL TIME WOULD BE 15 + 11 = 26 HOURS.
GOING BACK UP TO THE TOP, LOOKING AT TASK ONE,
THE CRITICAL TIME WOULD BE 17 + 4 = 21 HOURS.
LOOKING AT TASK 6, THE CRITICAL TIME WOULD BE 9 + 10 = 19 HOURS.
AND LOOKING AT TASK TWO,
NOTICE HOW THERE ARE TWO PATHS TO CONSIDER.
IF WE COME FROM THIS DIRECTION,
THE CRITICAL TIME WOULD BE 17 + 5 = 22 HOURS,
BUT IF WE USE THIS PATH,
THE CRITICAL TIME WOULD BE 19 + 5 = 24 HOURS.
WE USE THE LARGER OF THE TWO VALUES.
THEREFORE, THE CRITICAL TIME IS 24 HOURS.
AND NOW FROM HERE WE CAN MAKE OUR PRIORITY LIST.
WE'LL LIST THE TASK WITH THE HIGHEST CRITICAL TIME
TO THE LOWEST CRITICAL TIME.
THE HIGHEST CRITICAL TIME IS 26 HOURS STARTING AT TASK 3.
SO TASK THREE IS FIRST ON THE PRIORITY LIST.
THAT WOULD BE FOLLOWED BY TASK 2 AT 24 HOURS
AND THEN TASK 1 AT 21 HOURS.
SO TASK TWO IS NEXT, FOLLOWED BY TASK ONE.
NEXT, WE HAVE TASK 6 THAT HAS A CRITICAL TIME OF 19 HOURS,
FOLLOWED BY TASK 5 AT 17 HOURS.
SO WE HAVE TASK SIX, FOLLOWED BY TASK FIVE.
NEXT, TASK 7 HAS A CRITICAL TIME OF 15 HOURS.
NEXT, NOTICE HOW TASK 8 AND TASK 9
BOTH HAVE CRITICAL TIMES OF 9 HOURS, WHICH WOULD BE THE SAME,
BUT TYPICALLY WE WOULD LIST THE TASK
WITH THE LOWEST NUMBER FIRST.
SO I'M GOING TO LIST TASK EIGHT FIRST AND THEN TASK NINE SECOND.
BUT BECAUSE I DO HAVE THE SAME CRITICAL TIME,
IT REALLY DOESN'T MATTER.
THAT LEAVES US WITH TASK FOUR
WITH A CRITICAL TIME OF THREE HOURS.
AND THEN TASK TEN AT TWO HOURS.
SO WE HAVE TASK FOUR, FOLLOWED BY TASK TEN.
THIS IS HOW WE CREATE A PRIORITY LIST
USING THE BACKFLOW ALGORITHM.
I HOPE YOU FOUND THIS HELPFUL.