Online PHP editor | refs for 9WaiB

<?php function findWayPoints(array $lookup, $start, $end, array $path = []): ?array { if (isset($lookup[$start][$end])) { return $path; // full path found; no need to further recurse } foreach ($lookup[$start] ?? [] as $conn => $irrelevant) { $result = findWayPoints( array_diff_key($lookup, [$start => null]), // eliminate circular/infinite recursion $conn, // change starting node in next call $end, array_merge($path, [$conn]) // append current match to path ); if ($result !== null) { return $result; } } return null; // dead end; kill path } function buildLookup($nodes) { $lookup = []; foreach ($nodes as $k => [$connections]) { foreach (explode(' ', $connections) as $conn) { $lookup[$k][$conn] = true; $lookup[$conn][$k] = true; } } return $lookup; } $nodes = [ 'f' => ['d g'], 'b' => ['a d'], 'g' => ['i'], 'd' => ['c e'], 'i' => ['h'] ]; $lookup = buildLookup($nodes); echo json_encode(findWayPoints($lookup, 'h', 'f')); echo "\n---\n"; echo json_encode(findWayPoints($lookup, 'f', 'h')); echo "\n---\n"; echo json_encode(findWayPoints($lookup, 'a', 'c')); echo "\n---\n"; echo json_encode(findWayPoints($lookup, 'a', 'b')); echo "\n---\n"; echo json_encode(findWayPoints($lookup, 'a', 'h')); echo "\n---\n"; echo json_encode(findWayPoints($lookup, 'i', 'j'));