- WELCOME TO A LESSON ON THE SORTED EDGES ALGORITHM THAT CAN
BE USED TO TRY TO FIND THE OPTIMAL OR LOWEST COST
HAMILTONIAN CIRCUIT. SO AS AN ALTERNATIVE OUR NEXT APPROACH
WE'LL STEP BACK AND LOOK AT THE BIG PICTURE. WE DETERMINE A
HAMILTONIAN CIRCUIT BY SELECTING EDGES WITH THE
LEAST WEIGHT AND THEN FILL IN THE GAPS AS NEEDED. AND HERE
ARE THE STEPS FOR THE SORTED EDGES ALGORITHM,
ALSO KNOWN AS THE CHEAPEST LINK ALGORITHM. STEP ONE, WE SELECT
THE CHEAPEST UNUSED EDGE IN THE GRAPH, STEP TWO, WE
REPEAT STEP ONE ADDING THE CHEAPEST UNUSED EDGE TO THE
CIRCUIT UNLESS "A" ADDING THE EDGE WOULD CREATE A CIRCUIT
THAT DOESN'T CONTAIN ALL VERTICES WHERE B ADDING THE
EDGE WOULD GIVE A VERTEX DEGREE THREE. STEP THREE, REPEAT UNTIL
A CIRCUIT CONTAINING ALL VERTICES IS FORMED. SO
IN OUR PAST SEVERAL LESSONS, WE FOUND THE HAMILTONIAN CIRCUITS
OF THE GIVEN GRAPH HERE WE'RE USING THE BRUTE FORCE ALGORITHM
WE FOUND THE CIRCUIT, "A," B, C, E, D, "A,"
WITH A TOTAL WEIGHT OF 19 WHICH WE KNEW WAS THE LOWEST COST
HAMILTONIAN CIRCUIT. THEN WE APPLIED THE NEAREST NEIGHBOR
ALGORITHM AND FOUND THE HAMILTONIAN CIRCUIT "A," E, D,
C, B, "A" TO HAVE TOTAL WEIGHT OF 21 AND THEN
IN OUR LAST LESSON, WE APPLIED THE REPEATED NEAREST NEIGHBOR
ALGORITHM AND FOUND THE CIRCUIT "A," B, C, E, D, "A,"
WITH A TOTAL WEIGHT OF 19.
WE BEGIN BY SELECTING THE CHEAPEST EDGE WHICH WOULD BE
EDGE D, E AND NOW WE SELECT THE NEXT CHEAPEST EDGE AS LONG AS IT
DOESN'T VIOLATE CONDITION "A"
OR B. BUT NOTICE HOW IN THIS CASE EDGE E,
"A" AND EDGE E, C BOTH HAVE A WEIGHT OF TWO
WHICH MEANS WHEN WE APPLY THE SORTED EDGES ALGORITHM,
WE -- ENDING UP WITH TWO CIRCUITS. LET'S FIRST TAKE
A LOOK AT THE CIRCUIT THAT WOULD INCLUDE EDGE E,
"A." AND JUST TO REMIND OURSELVES,
WE'LL HAVE TO PERFORM THIS ALGORITHM A SECOND TIME. NOTICE
HOW THIS CIRCUIT WOULD CONTAIN D, E, "A" AND IF WE USED EDGE
E, C, THE CIRCUIT WOULD CONTAIN D, E,
C. SO WE'LL FIND THIS CIRCUIT FIRST, AND THEN COME BACK AND
FIND THE SECOND. NOW WE WANT TO SELECT THE NEXT CHEAPEST EDGE
AS LONG AS ADDING THE EDGE WOULD NOT CREATE A CIRCUIT THAT
DOESN'T CONTAIN ALL VERTICES OR ANY OF THE EDGE WOULD GIVE A
VERTEX DEGREE THREE. NOTICE HOW THE NEXT CHEAPEST EDGE WOULD BE
EDGE E. C. BUT WE CAN'T USE THIS EDGE BECAUSE THAT WOULD
GIVE VERTEX E A DEGREE THREE. SO THE NEXT CHEAPEST EDGE WOULD
BE EDGE E, B WITH A WEIGHT OF THREE, BUT AGAIN WE CAN'T
USE THIS EDGE BECAUSE THIS AGAIN WOULD GIVE VERTEX E,
DEGREE THREE. SO THE NEXT CHEAPEST EDGE WOULD BE EDGE
"A," D, WITH A WEIGHT OF FOUR. WE ALSO CAN'T USE EDGE "A," D
BECAUSE THIS WOULD CREATE A CIRCUIT THAT DOESN'T CONTAIN
ALL VERTICES. SO FINALLY THE NEXT CHEAPEST EDGE WOULD BE
EDGE "A," B WITH A WEIGHT OF FIVE. THE NEXT CHEAPEST EDGE
WOULD BE EDGE C, D WITH A WEIGHT OF SIX, AND
FINALLY, EDGE B, C WITH A WEIGHT OF SEVEN TO FORM
OUR HAMILTONIAN CIRCUIT. SO IF WE START AT VERTEX D,
WE WOULD HAVE D, E, "A," B, C, D WITH A TOTAL WEIGHT OF 1 + 2
+ 5 + 7 + 6 WHICH IS 21. NOW LET'S GO BACK AND FIND THE
SECOND POSSIBLE CIRCUIT. AGAIN WE KNOW WE'RE GOING TO START
WITH EDGE E, D BUT NOW INSTEAD OF USING EDGE E,
"A," WE'LL USE EDGE E, C THAT HAS THE SAME WEIGHT
OF TWO FOR OUR NEXT CHOICE. THE NEXT CHEAPEST EDGE WOULD BE
EDGE E, "A," WE CAN'T USE THAT BECAUSE IT GIVES VERTEX E
DEGREE THREE. THE SAME WITH EDGE E, B, SO THE NEXT
CHEAPEST EDGE WOULD BE EDGE "A," D WITH A WEIGHT OF FOUR.
NEXT CHEAPEST EDGE WOULD BE EDGE "A," B WITH A WEIGHT
OF FIVE, AND THEN FINALLY EDGE B, C WITH A WEIGHT
OF SEVEN. SO AGAIN STARTING WITH VERTEX D,
WE'D HAVE THE CIRCUIT D, E, C, B, "A," D WITH A TOTAL WEIGHT
OF 1 + 2 + 7 + 5 + 4 WHICH IS 19. SO OF COURSE, SO
OF COURSE WE'D USE THE CIRCUIT WITH THE LEAST WEIGHT THE
SECOND CIRCUIT HERE. BUT LOOKING BACK
AT THE DIRECTIONS, IT DOES ASK US
TO GIVE THE CIRCUIT STARTING WITH VERTEX "A." SO LET'S GO
AHEAD AND REWRITE THIS. WE'D ACTUALLY WRITE THE CIRCUIT
STARTING AT "A" AS "A," D, THEN VERTEX E, C, B,
"A." WE COULD ALSO GIVE THIS IN THE REVERSE ORDER AS A
DUPLICATE CIRCUIT AS "A," B, C, E, D, "A." SO IF WE ADD THIS
TO OUR CHART, NOTICE HOW THE SORTED EDGE ALGORITHM DID GIVE
US THE OPTIMAL OR LOWEST COST HAMILTONIAN CIRCUIT.
BUT WE SHOULD RECOGNIZE THIS MAY NOT ALWAYS BE THE CASE.
LET'S TAKE A LOOK AT ONE MORE EXAMPLE. WE'D BEGIN
BY SELECTING THE CHEAPEST EDGE OR THE EDGE WITH THE LEAST
WEIGHT WHICH WOULD BE EDGE "A," C WITH A WEIGHT OF THREE. THE
NEXT CHEAPEST EDGE WOULD BE EDGE B, C WITH A WEIGHT
OF FOUR, THE NEXT CHEAPEST EDGE WOULD BE EDGE "A," D
WITH A WEIGHT OF FIVE, THE NEXT CHEAPEST EDGE WOULD BE EDGE B,
D WHICH WE CANNOT USE BECAUSE IT WOULD CREATE A CIRCUIT THAT
DOESN'T CONTAIN ALL VERTICES. SO WE CAN'T USE EDGE B, D, SO
WE'LL NEXT CONSIDER EDGE "A," B WITH A WEIGHT OF SEVEN. AGAIN
WE CANNOT USE THAT EITHER BECAUSE ONCE AGAIN IT WILL FORM
A CIRCUIT THAT DOESN'T CONTAIN ALL VERTICES. SO THE NEXT
CHEAPEST EDGE WOULD BE EDGE B, E WITH A WEIGHT OF NINE WHICH
WE CAN USE. NOTICE HOW THERE ARE NO VERTICES WHERE THESE
EDGES CROSS. THE NEXT CHEAPEST EDGE WOULD BE EDGE "A," E
WITH A WEIGHT OF 10 WHICH WE CANNOT USE BECAUSE NOTICE HOW
THIS WOULD GIVE VERTEX "A" DEGREE THREE. SO THE NEXT
CHEAPEST EDGE WOULD BE EDGE C, E WITH A WEIGHT OF 12, WHICH
AGAIN WE CANNOT USE BECAUSE THAT WOULD GIVE VERTEX C A
DEGREE THREE. THE NEXT CHEAPEST EDGE WOULD BE EDGE D, E
WITH A WEIGHT OF 14 WHICH DOES COMPLETE OUR CIRCUIT. SO AGAIN
IF WE LIST THE CIRCUIT STARTING AT VERTEX "A," WE'LL GO
FROM "A" TO C TO B, TO E, TO D AND FINALLY BACK TO "A."
SO AGAIN WE'D HAVE "A," C, B, E, D,
"A." AND NOW LET'S FIND THE WEIGHT, THAT WOULD BE 3 + 4 +
9 + 14 + 5 WHICH IS 35.
AND WE SHOULD ALSO RECOGNIZE THERE
WOULD BE A DUPLICATE CIRCUIT IN THE REVERSE ORDER. WE COULD
GIVE THE SAME CIRCUIT AS "A," D, E, B, C, "A."
I DID HAVE ONE MORE EXAMPLE BUT I THINK WE'RE SHORT ON TIME
SO WE'LL STOP HERE.
I HOPE YOU FOUND THIS HELPFUL.