function [Tour weight] = TSPNearNbr(W,start)
%[Tour weight] = TSPNearNbr(W,start)
%Program for the nearest neighbor algorithm for the travelling salesman
%problem.
%Inputs: the price matrix W for a traveling salesman problem.  Optional 
%second input variable start allows the user to prescribe the vertex number
%for the start of the tour.  
%Outputs: A vector Tour containing a tour and its associated weight using the
%nearest neighbor heuristic.  

%Set start to default value 1 if not specified
if nargin < 2, start =1; end

[n m] = size(W);%n = m = number of vertices
%Initialize Tour and Vector of unused vertices
Tour=[start]; Unused = setdiff(1:n,start);
Last = start; %initialize most recent vertex in tour.
weight=0; %initialize weight

while length(Tour)<n
    mindist=Inf; %initialize minimum distance to nearest neighbor
    for i=1:length(Unused)
        if W(Last, Unused(i))<mindist
            mindist=W(Last, Unused(i)); Next=Unused(i);
        end
    end
    Tour =[Tour Next]; Unused = setdiff(Unused, Next);
    weight = weight + mindist;  Last = Next;
end
%finalize Tour and weight
Tour = [Tour start]; weight = weight + W(start,Last);
       
    
    