function [lowprice, Rts]=TSP_Brute(W)
% Solves the traveling salesman problem by brute-force.
% Assumes home city is #1
% one input variable:  W = edge weight matrix
% two output variables:  (default)  lowprice = lowest possible total
% price of a trip starting in #1, visiting all cities, and ending
% back in #1.  Rts = a matrix of all routes on which this lowest 
% price is realized; each row corresponds to an optimal route   
[n,m]=size(W);
Per=perms(2:n);
[p, r]=size(Per); %Note: r = n - 1
for i=1:p
   x(1)=W(1,Per(i,1));  %Price of home to first city.  
   for j=1:r-1
      x(j+1)=W(Per(i,j),Per(i,j+1));
   end
   x(n)=W(Per(i,n-1),1); %Price from last city back home.    
   price(i)=sum(x);
end
lowprice = min(price);
lowperms =Per(find(price == lowprice),:); %Collect lowest price permutations.  
[a b]= size(lowperms);
Rts=ones(a,b+2);,  %Initiate correct size matrix for rts.  
Rts(:,2:(b+1))=lowperms; %Transplant lowperms in middle columns of rts.