Programming the Nearest Neighbour Algorithm

CBASIC

The Code

This code was written on an fx-9860gii using the C-Basic software

    
'ProgramMode:RUN
[[1Exp6,27,12,23,74][27,1Exp6,47,15,71][12,47,1Exp6,28,87][23,15,28,1Exp6,75][74,71,87,75,1Exp6]]->Mat A
Mat A
1->S
5->L
Mat A->Mat B
{2,L}->Dim Mat V
Fill(0,Mat V)

For 1->J To L
1Exp6->Mat B[S,J]
Next
1->V
S->Mat V[1,V]
Lbl R
1Exp6->T
For 1->I To L
If Mat B[I,Mat V[1,V]]<=T
Then 
Mat B[I,Mat V[1,V]]->T
I->n
IfEnd
Next
V+1->V
n->Mat V[1,V]
T->Mat V[2,V]
For 1->J To L
1Exp6->Mat B[Mat V[1,V],J]
Next
V=L=>Goto E
Goto R
Lbl E
Mat V
Stop
        
    
    

Code Breakdown

This code defines a distance matrix that looks like so:

        A  B  C  D  E     
        +---------------   
       A|-  27 12 23 74    
       B|27 -  47 15 71    
       C|12 47 -  28 87    
       D|23 15 28 -  75    
       E|74 71 87 75 - 
    

I substituted the "-" with 1x10^6 because this is a reasonably large number, that won't be exceeded by common distance matrices.

Defines the starting vertex (S) as 1. Defines the length of the square distance matrix (L) to be 5. Creates a back-up of Matrix A into Matrix B

Creates a 2xL (dimension length) matrix, which will store the order of visited vertices. Makes all the values equal to 0.

"Crosses" out the starting vertex row, essentially making all its values too big to be chosen!

Counts the number of visited vertices in the variable V. Clearly, when starting at a vertex, the number of visited vertices is 1. It stores the first vertex into the first row of the Mat V

- Creates a new subroutine labeled "R".
- Sets the lowest value of the list to be 1e6.
- Iterates through all the variables in the most recently visited vertex.
- Stores the smallest value in T, and it's position as n.

- Increases the number of visited vertices by 1.
- Stores the vertex which was visited in the matrix V, row 1
- Stores the distance in the matrix V, row 2

"Crosses out" the last vertex to be visited

If all vertices have been visited, finish loop and print the algorithm's result, else repeat