Shortest Unweighted Path

Problem Description

On November 1st, as people remember All Saints' Day, imagine a scenario where a collection of towns is connected by direct roads. The towns and roads form an unweighted, undirected graph. Your task is to help find the shortest route (in terms of the number of roads traveled) between two given towns using graph traversal techniques.

Task

Write a function that, given an adjacency list representation of an undirected graph, a start town, and a destination town, returns the shortest path between these two towns. If no path exists, the function should return an empty array.

Input

• An adjacency list representing an undirected graph. For example:

  graph = {
      0: [1, 2],
      1: [0, 3],
      2: [0, 3],
      3: [1, 2]
  }
  

• A start node (town).

• A destination node (town).

Output

• An array (or list) containing the sequence of nodes representing the shortest path from the start to the destination. If no valid path exists, return an empty array.

Example

For the graph provided above, if the start node is 0 and the destination is 3, then a valid shortest path is [0, 1, 3] or [0, 2, 3].

Starter Code

Below is some language-agnostic starter code to help you begin:

// Function Signature:
// function findShortestPath(graph, start, destination) { }

// Input: graph (object/dictionary), start (integer), destination (integer)
// Output: array of integers representing the shortest path, or an empty array if no path exists