# Graph Theory: Repeated Nearest Neighbor Algorithm (RNNA)

Articles, Blog 4 Comments

– WELCOME TO A LESSON ON THE REPEATED NEAREST NEIGHBOR

ALGORITHM. USING THE GRAPH HERE ON THE LEFT

IN A PREVIOUS LESSON, WE FOUND THE LOWEST COST

HAMILTONIAN CIRCUIT USING THE BRUTE FORCE ALGORITHM TO BE THE CIRCUIT “A,” B, C, E,

D, “A” TO HAVE A TOTAL WEIGHT OF 19. WE KNEW THIS WAS THE LOWEST COST

HAMILTONIAN CIRCUIT OR OPTIMAL HAMILTONIAN CIRCUIT BECAUSE REMEMBER THE BRUTE FORCE

METHOD IS THE ONLY METHOD THAT GUARANTEES TO FIND THE

LOWEST COST HAMILTONIAN CIRCUIT. THEN WE FOUND THE HAMILTONIAN

CIRCUIT USING THE NEAREST NEIGHBOR

ALGORITHM TO BE “A,” E, D, C, B, “A” WHICH HAD A TOTAL WEIGHT OF 21, NOT THE LOWEST COST

HAMILTONIAN CIRCUIT. BUT WE CAN IMPROVE ON THE

NEAREST NEIGHBOR ALGORITHM BY APPLYING THE ALGORITHM

FROM EACH VERTEX AND THIS IS THE REPEATED

NEAREST NEIGHBOR ALGORITHM. SO STEP ONE WE PERFORM THE

NEAREST NEIGHBOR ALGORITHM STARTING IN EACH VERTEX AND THEN TWO, WE CHOOSE

THE CIRCUIT PRODUCED WITH A MINIMAL TOTAL WEIGHT. AND JUST TO REVIEW, TO APPLY

THE NEAREST NEIGHBOR ALGORITHM, STEP ONE, WE START AT A VERTEX, STEP TWO, WE MOVE TO THE NEAREST

UNVISITED VERTEX USING THE EDGE WITH THE SMALLEST WEIGHT AND THEN THREE, WE REPEAT

UNTIL THE CIRCUIT IS COMPLETE. SO LET’S GO AHEAD AND APPLY THE REPEATED NEAREST NEIGHBOR

ALGORITHM TO THE SAME GRAPH. SO WE’LL BEGIN AT VERTEX “A” AND NOTICE HOW WE CAN VISIT

VERTEX B, E, OR D BUT HE IS THE CLOSEST BECAUSE

EDGE “A,” E HAS A WEIGHT OF TWO. SO WE’LL GO FROM “A” TO E AND NOW FROM HERE IT DOES APPEAR

LIKE WE HAVE THREE CHOICES BUT WE REALLY ONLY HAVE TWO

BECAUSE IF WE WENT TO C, WE COULD NOT VISIT D AND B

AND THEN RETURN TO “A” WITHOUT USING OUR VERTEX

MORE THAN ONCE. SO WE CAN VISIT EITHER B OR D. NOTICE EDGE E, D

IS A WEIGHT OF ONE, SO WE’LL VISIT D NEXT

AND NOW WE ONLY HAVE ONE CHOICE, WE HAVE TO VISIT C, B,

AND THEN “A.” SO WE HAVE THE CIRCUIT

“A,” E, D, AND THEN C, B, “A.” SO THE TOTAL WEIGHT WOULD BE

2 + 1 + 6 + 7 + 5 WHICH IS EQUAL TO A TOTAL WEIGHT

OF 21. NOW WE’LL START AT VERTEX B, THE CLOSEST VERTEX TO VERTEX B

IS GOING TO BE VERTEX E BECAUSE EDGE B, E

HAS A WEIGHT OF 3. AND AGAIN HERE WE ONLY HAVE

TWO CHOICES, WE CAN VISIT EITHER “A” OR C BUT NOTICE HOW THE TWO EDGES

HAVE THE SAME WEIGHT SO WE’RE ACTUALLY GOING TO HAVE

TWO CIRCUITS STARTING AT VERTEX B. LET’S FIRST VISIT “A”

SO WE’LL GO FROM E TO “A.” FROM HERE WE HAVE ONE CHOICE WE

HAVE TO VISIT VERTEX D, THEN C, AND THEN B. SO THIS GIVES US THE CIRCUIT

B, E, “A,” D, C, B WHICH WOULD HAVE A TOTAL WEIGHT

OF 3 + 2 + 4 + 6 + 7 WHICH IS EQUAL TO 22. AND AGAIN WE’LL HAVE

ANOTHER CIRCUIT STARTING WITH B, AND THEN E, REMEMBER HERE WE WENT FROM E TO

“A” NOW WE’LL GO FROM E TO C. SO FROM B WE VISIT E, AND THEN BECAUSE THESE TWO EDGES

HAVE THE SAME WEIGHT AND WE JUST WENT TO “A,”, WE’LL NOW GO TO C. AND NOW WE HAVE ONE CHOICE WE’LL

GO FROM C TO D, FROM D TO “A” AND “A” BACK TO B. SO THE CIRCUIT IS B, E, C,

D, “A,” B. SO THE WEIGHT WOULD BE 3 + 2 + 6

+ 4 + 5 GIVING US A TOTAL WEIGHT OF 20 AND NOW WE’LL MOVE

TO A VERTEX C. STARTING AT VERTEX C, THE

NEAREST VERTEX WOULD BE VERTEX E SINCE EDGE C, E

HAS A WEIGHT OF TWO. FROM HERE THE NEAREST VERTEX IS

VERTEX D WITH A WEIGHT OF ONE. FROM HERE WE HAVE ONE CHOICE

WE HAVE TO VISIT “A” THEN B, THEN BACK TO C. SO OUR CIRCUIT IS C, E, D,

“A,” B, C WHICH HAS A WEIGHT OF 2 + 1 + 4

+ 5 + 7 WHICH IS EQUAL TO 19. AND NOW WE’LL MOVE TO VERTEX D. SO STARTING AT VERTEX D,

THE NEAREST VERTEX IS VERTEX E, EDGE D, E HAS A WEIGHT OF ONE. AND AGAIN FROM HERE,

WE ONLY HAVE TWO CHOICES, WE CAN VISIT “A” OR C AND NOTICE HOW THESE TWO EDGES

HAVE THE SAME WEIGHT SO AGAIN WE’LL HAVE TWO CIRCUITS

STARTING AT VERTEX D. LET’S FIRST VISIT VERTEX “A.” NOW WE ONLY HAVE ONE CHOICE, WE HAVE TO VISIT VERTEX B

THEN C, AND THEN D. SO THIS GIVES US THE CIRCUIT

D, E, “A,” B, C, D. SO WE’D HAVE TOTAL WEIGHT OF

1 + 2 + 5 + 7 + 6 WHICH IS EQUAL TO 21. AND NOW INSTEAD OF GOING

FROM E TO “A,” WE’LL NOW GO FROM E TO C. SO AGAIN BECAUSE THESE TWO EDGES

HAVE THE SAME WEIGHT AND WE JUST VISITED “A,”

WE’LL NOW VISIT C. AND NOW WE ONLY HAVE ONE CHOICE,

WE HAVE TO VISIT B, THEN “A,” AND THEN D. SO THE CIRCUIT WOULD BE

D, E, C, B, “A,” D. SO THE TOTAL WEIGHT WOULD BE

1 + 2 + 7 + 5 + 4 WHICH IS 19. AND FINALLY WE NEED TO START

AT VERTEX E. SO STARTING AT VERTEX E,

THE NEAREST VERTEX IS VERTEX D, EDGE E, D HAS A WEIGHT OF ONE. FROM HERE WE CAN VISIT EITHER

VERTEX “A” OR C BUT SINCE EDGE D, “A”

HAS A WEIGHT OF FOUR, WE’LL VISIT VERTEX “A.” FROM HERE WE HAVE TO GO

TO VERTEX B, THEN C, THEN BACK TO E. SO WE HAVE THE CIRCUIT

E, D, “A,” B, C, E WITH THE TOTAL WEIGHT OF 1 + 4

+ 5 + 7 + 2 WHICH IS ALSO 19. AND NOW WE SELECT THE CIRCUIT

WITH THE LEAST WEIGHT, BUT NOTICE HOW THERE ARE

THREE CIRCUITS HERE THAT HAVE A TOTAL WEIGHT OF 19. SO LET’S TAKE A CLOSER LOOK

AT THESE THREE CIRCUITS. IN OUR PREVIOUS EXAMPLES, WE

ALWAYS STARTED AT VERTEX “A” PLUS WE WRITE THESE CIRCUITS

STARTING AT VERTEX “A” TO THE CIRCUITS FOUND USING

THE DIFFERENT METHODS. SO LOOKING AT THIS CIRCUIT HERE,

IF WE START AT VERTEX “A,” NOTICE HOW WE’D GO

FROM “A” TO B TO C AND THEN FROM C, NOTICE HOW WE

WOULD VISIT VERTEX E, D, AND THEN RETURN TO “A.” NOW LET’S TAKE A LOOK AT THIS

CIRCUIT HERE STARTING AT “A” WE’D GO FROM VERTEX “A”

TO VERTEX D AND THEN FROM D WE’D VISIT

VERTEX E, C, B AND THEN BACK TO “A.” AND THESE CIRCUITS

ARE ACTUALLY DUPLICATES, THEY’RE JUST GIVEN

IN THE REVERSE ORDER. NOTICE “A,” B, C, E, D, “A,”

IN REVERSE ORDER WOULD BE THE SAME CIRCUIT

AS “A,” D, E, C, B, “A.” NOW LET’S TAKE A LOOK

AT THIS LAST CIRCUIT, AGAIN STARTING AT VERTEX “A,” WE’D HAVE THE CIRCUIT “A,” B, C

WHICH WE HAVE HERE, E, AND THEN D, AND THEN “A,” WHICH IS THE SAME

AS THIS CIRCUIT HERE. SO IF WE COMPARE THIS CIRCUIT

TO OUR PREVIOUS RESULTS, WE SEE HERE AT THE BOTTOM, NOTICE HOW THIS IS

THE SAME CIRCUIT THAT WE FOUND USING BRUTE FORCE WHICH WE KNOW IS THE — OR

LOWEST COST HAMILTONIAN CIRCUIT. SO BY USING THE REPEATED

NEAREST NEIGHBOR ALGORITHM, WE DO HAVE A BETTER CHANCE, WE DO HAVE A BETTER CHANCE

OF DETERMINING THE LOWEST COST OR OPTIMAL HAMILTONIAN CIRCUIT. I THINK WE’LL HAVE TO STOP HERE

FOR THIS LESSON. I HOPE YOU FOUND THIS HELPFUL.

xinwei hePost authornice tutorial i learned a lot about graph

Mohanad AbusabtPost authorawesome!!!

Drift_Team_NVGPost authorjesus fucking christ move away from your microphone when you breath

Abby HansenPost authorwhen starting at the B vertex, then moving to the E vertex, why can't E move to D. It seems like E to D has the lightest weight, compared to E to A and E to C , both with weight of 2?