RWC: Path Between Points

path-between-points.js

/**
 * @typedef {object} Point
 * @property {string} name
 * @property {string[]} connections
 */

/** @type {Point[]} */
const listOfPoints = [
	{ name: 'A', connections: ['B', 'C'] },
	{ name: 'B', connections: ['A', 'E'] },
	{ name: 'C', connections: ['A', 'D'] },
	{ name: 'D', connections: ['C'] },
	{ name: 'E', connections: ['B', 'F'] },
	{ name: 'F', connections: ['E'] },
]

/**
 * Comparator/sort function for sorting two arrays by their length in descending order.
 * @param {string[]} a 
 * @param {string[]} b 
 * @returns {number} relative order between the two arrays
 */
function byLength(a, b) {
	return b.length - a.length;
}

/**
 * Recursively determines the shortest path from the current point to the desired end point.
 * If no paths between the two points exist, aborts with `false`.
 * Does not revisit visited points (doing so wouldn't create the shortest path, and would risk cycles)
 * @param {Object<string, string[]>} normalizedPoints 
 * @param {string} currentPoint 
 * @param {string} end 
 * @param {string[]} visited
 * @returns {string[] | false}
 */
function getShortestPathToPoint(normalizedPoints, currentPoint, end, visited) {
	// Base case: you've reached the end
	if (currentPoint === end) {
		return [end];
	}

	// Get possible connections
	const connections = normalizedPoints[currentPoint].filter(point => !visited.includes(point));
	
	// No more possible connections? Abort.
	if (connections.length === 0) {
		return false;
	}

	const viablePaths = connections
		.map(nextPoint => getShortestPathToPoint(normalizedPoints, nextPoint, end, [...visited, currentPoint]))
		.filter(path => (path !== false));

	// None of the connections were fruitful? Abort.
	if (viablePaths.length === 0) {
		return false;
	}

	// At least one connection proved successful! Return the shortest one.
	const [shortestPath] = viablePaths.sort(byLength);
	return [currentPoint, ...shortestPath];
}

/**
 * Prints the shortest path between two points, or "no path" if none exist
 * @param {Point[]} points
 * @param {string} start 
 * @param {string} end
 */
function pathBetweenPoints(points, start, end) {
	const normalizedPoints = points.reduce((normalized, point) => {
		return {...normalized, [point.name]: point.connections};
	}, {});

	const shortestPath = getShortestPathToPoint(normalizedPoints, start, end, []);

	shortestPath ?
		console.log(shortestPath.join(' -> ')) :
		console.log('no path');
}

pathBetweenPoints(listOfPoints, 'A', 'F');
pathBetweenPoints(listOfPoints, 'D', 'B');