TSP tsp nearest neighbor algorithm. Gets the shortest path between all nodes, starting at the specified index (default 0), and orders them.

nearNeighbor.js

// needed for the algorithm
// cartesian distance formula
export const Distance = (x1, y1, x2, y2) => {
    return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
};

// tsp nearest neighbor algorithm
// gets the shortest path between all nodes
// starting at the index of start_index
// orders the nodes based on this path
export const TSPNearNeighbor = (points, start_index = 0) => {
    const result = [points[start_index]];
    const visited_indices = [start_index];
    let current_index = start_index;

    while (result.length < points.length) {
        let short_distance = Infinity;
        let short_index = -1;

        for (let i = 0; i < points.length; i++) {
            if (i === current_index || visited_indices.includes(i)) {
                continue;
            }
            const current = points[current_index];
            const next = points[i];
            const distance = Distance(
                next.x,
                next.y,
                current.x,
                current.y
            );
            if (distance < short_distance) {
                short_distance = distance;
                short_index = i;
            }
        }
        if (short_index > -1 && short_distance !== Infinity) {
            result.push(points[short_index]);
            visited_indices.push(short_index);
        }
    }
    
  return result;
};