function [Tour weight] = TSPCheapestInsertion(W,start)
%[Tour weight] = TSPCheapestInsertion(W,start)
%Program for the nearest insertion heuristic for the traveling 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
    cheapestDiff = Inf; %initialize differential
   if length(Tour) > 1
    for j = 1:length(REMAIN)
        vertex = REMAIN(j);
        %now look for the best place to insert vertex it in current Tour
        MinWeightDiff = Inf; %Initialize weight differential for this vertex
        InsertPoint=Tour(1); InsertIndex = 1;%Initialize insert point and index 
        for i=1:length(Tour)-1
           weightDiff = W(Tour(i),vertex)+W(vertex,Tour(i+1))-W(Tour(i),Tour(i+1));
           if weightDiff<MinWeightDiff
              InsertPoint=Tour(i); MinWeightDiff = weightDiff; InsertIndex=i;
           end
        end
        if MinWeightDiff < cheapestDiff
            cheapVertex = vertex; cheapInsertPoint = InsertPoint;
            cheapestDiff = MinWeightDiff;
        end
    end
   else %if tour is just starting, insert the closest vertex
       [a b] = min(W(start,REMAIN));
       ind = b(1); cheapVertex = REMAIN(ind);
   end
       
    
    if length(Tour)==1, Tour = [Tour cheapVertex Tour]; weight=2*W(Tour(1),cheapVertex);  ...
        REMAIN = setdiff(REMAIN,cheapVertex);
    else
      Tour(InsertIndex+1:length(Tour)+1)=[cheapVertex Tour(InsertIndex+1:length(Tour))];
      weight=weight+MinWeightDiff; REMAIN = setdiff(REMAIN,cheapVertex);
    end
end