function [Tour weight] = TSPNearInsertion(W,start)
%[Tour weight] = TSPNearInsertion(W,start)
%Program for the nearest insertion heuristic 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 insertion 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]; REMAIN = setdiff(1:n,start);
weight=0; %initialize weight

while length(Tour)<n+1
    %first find nearest vertex to current tour
    mindist=Inf; %initialize minimum distance to nearest neighbor
    Nearest = REMAIN(1); %initialize new vertex for insertion
    for i=1:length(REMAIN)
        Dist = min(W(REMAIN(i),Tour));
        if Dist<mindist
            Nearest = REMAIN(i);
            mindist=Dist; 
        end
    end
    %now look for the best place to insert new vertex it in current Tour
    MinWeightDiff = Inf; %Initialize weight differential
    InsertPoint=Tour(1); InsertIndex = 1;%Initialize insert point and index 
    for i=1:length(Tour)-1
        weightDiff = W(Tour(i),Nearest)+W(Nearest,Tour(i+1))-W(Tour(i),Tour(i+1));
        if weightDiff<MinWeightDiff
            InsertPoint=Tour(i); MinWeightDiff = weightDiff; InsertIndex=i;
        end
    end
    if length(Tour)==1, Tour = [Tour Nearest Tour]; weight=2*mindist;  ...
        REMAIN = setdiff(REMAIN,Nearest);
    else
      Tour(InsertIndex+1:length(Tour)+1)=[Nearest Tour(InsertIndex+1:length(Tour))];
      weight=weight+MinWeightDiff; REMAIN = setdiff(REMAIN,Nearest);
    end
end