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.