function [route,distance] = findRoute(start,destinations)
% findRoute Closest neighbor solution to traveling salesman problem.
%
% [route,distance] = findRoute(start,destinations) finds a "good enough"
% path from START that passes through all the destinations. ROUTE and
% DESTINATIONS are cell arrays of strings, and distance is the length of
% the route (not couting the distance from the last stop back to start).
%
% At each stage along the path, move to the nearest of the remaining
% destinations.

% Copyright 1984-2019 The MathWorks, Inc.
% All Rights Reserved.

    % Connect to the cache that stores the graph.
    c = mps.cache.connect('TravelingSalesman','Connection','ScratchPad');
    
    % If we can't load the distance data, we can't do any work.
    if loadDistanceData('ScratchPad','TravelingSalesman') == false
        error('Failed to load distance data. Cannot continue.');
    end
        
    % Retrieve the graph of destination distances from the cache.
    g = c.Distances;
    
    % The route always starts at the beginning.
    route = {start};
    distance = 0;
    current = start;
    
    % While we have not yet visited all destinations, look through the list
    % and find the closest one. Visit that one next. This produces a
    % non-optimal route that is often "good enough".
    while ~isempty(destinations)
        % Since we're going to be searching for the closest neighbor, track
        % the name and distance to the closest one we've seen so far.
        minDistance = Inf;
        nextSegment = {};
        % Look at all the neighbors and find the closest one.
        for n = 1:numel(destinations)
            % Graph algorithm shortest path works even if the graph is not
            % complete (paths between some nodes longer than length one).
            [p,d] = shortestpath(g,current,destinations{n});
            if d < minDistance
                nextSegment = p(2:end);
                minDistance = d;
            end
        end
        % Our next destination is nextSegment{end}. To avoid duplication,
        % remove that destination from the list.
        current = nextSegment{end};
        distance = distance + minDistance;
        destinations = setdiff(destinations,current);
        
        % Add the next segment to the route and continue until we've
        % visited all the destinations.
        route = [ route nextSegment ];  %#ok -- Can't a priori know length
    end
end