Route finder

The nearest neighbor (NN) algorithm constructs a route through a set of cities. It is a heuristic, a method for finding a candidate route without guaranteeing the shortest route. The algorithm starts at a random city and then moves to the nearest city that has not been visited yet. The algorithm continues this process until all the cities have been visited.

The algorithm can be implemented using a distance matrix that contains the distances between the cities. The algorithm starts at an origin city (possibly randomly selected) and then iteratively selects the nearest neighbor of the last city in the route until all the cities have been visited.

In this exercise, you will develop a route finder app that finds the best nearest neighbor route and its total distance using the NN algorithm.

Complete the questions in order and implement the functions in Python. The printing and route questions reuse the earlier functions. The dictionary questions repeat those tasks with a different representation.

Use at least two unique city names and a square, symmetric distance matrix with the same number of rows and columns as cities. Distances are nonnegative integer kilometers, and each city’s distance to itself is zero. Row and column positions follow the order in cities. In the dictionary representation, each city is an outer key and every destination is an inner key.

Once you have implemented the NN algorithm, see in Figure 1 how to use the folium library to display the routes on a map.

Figure 1: Using folium to display routes on a map.

Creating the distance matrix

The first step is to create a distance matrix that contains the distances between the cities. The distance matrix is a list of lists where each element represents the distance between two cities. The distance matrix is symmetric, meaning that the distance between city A and city B is the same as the distance between city B and city A.

Parse the distance matrix of the Dutch cities at Geodatos and use it in the questions. The saved distance table keeps the same eight-city data available for this exercise. Distances are in kilometers. The first row names the destination cities and the first column names the origin cities. Keep that order in cities and use the numeric cells as dist_matrix.

To parse it you can:

  • Copy the table and format it as a list of lists in Python (use shortcuts to format it faster).
  • Copy the data into Copilot chat and ask it to format it as a list of lists in Python.

Finding the distance between two cities

Create a function that returns the distance between two cities. The function will take two strings origin and destination, a list of lists dist_matrix that represents the distance matrix of the cities, and a list of strings cities. The function should return the distance between the two cities.

Function signature: find_distance_between(origin: str, destination: str, dist_matrix: list[list[int]], cities: list[str]) -> int

Parameters:

  • origin (str): A string representing the origin city.
  • destination (str): A string representing the destination city.
  • dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
  • cities (list[str]): A list of strings representing the cities.

Returns:

  • int: The distance between the two cities.

Constraints:

  • The origin and destination will be in the list of cities.
  • The distance matrix will have a minimum size of 2x2.

Example:

Listing 1 shows a call that finds the distance between A and B.

Listing 1: Find the distance between two cities. 
cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

origin = 'A'
destination = 'B'

distance = find_distance_between(origin, destination, dist_matrix, cities)
print(distance)  # Output: 1

Printing all distances

Create a function that returns all the distances between the cities. The function will take a list of lists dist_matrix that represents the distance matrix of the cities and a list of strings cities. The function should return a string that contains all the distances between the cities as shown in the example below.

Tip: Use the find_distance_between function.

Function signature: print_all_distances(dist_matrix: list[list[int]], cities: list[str]) -> str

Parameters:

  • dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
  • cities (list[str]): A list of strings representing the cities.

Returns:

  • str: A string that contains all the distances between the cities.

Constraints:

  • The distance matrix will have a minimum size of 2x2.

Example:

Listing 2 shows the returned string and the required order of the city pairs.

Listing 2: Return the distances between every pair of distinct cities. 
cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

distances_str = print_all_distances(dist_matrix, cities)
print(distances_str)  # Output: 'A -> B: 1\nA -> C: 2\nB -> A: 1\nB -> C: 3\nC -> A: 2\nC -> B: 3\n'

Finding the nearest neighbor

Create a function that returns the nearest neighbor of the last element in the route. The function will take a tuple of strings route and a list of lists dist_matrix that represents the distance matrix of the cities. The function should return the nearest neighbor of the last element in the route.

Function signature: find_nearest_neighbor(route: tuple[str, ...], dist_matrix: list[list[int]], cities: list[str]) -> str

Parameters:

  • route (tuple[str, ...]): A tuple of strings representing the route.
  • dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.
  • cities (list[str]): A list of strings representing the cities.

Returns:

  • str: The nearest neighbor of the last element in the route.

Constraints:

  • The length of the route will be at least 1.
  • The route contains distinct cities from cities and is shorter than the cities list, so an unvisited city remains.
  • The nearest neighbor cannot be in the route. If several unvisited cities are equally near, use a consistent tie rule.
  • The distance matrix will have a minimum size of 2x2.

Example:

Listing 3 shows the nearest neighbor when the route starts at A.

Listing 3: Find an unvisited city nearest to the end of a route. 
cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

route = ('A', )


nn = find_nearest_neighbor(route, dist_matrix, cities)
print(nn)  # Output: 'B'

Finding the best nearest neighbor route

Create a function that returns the best nearest neighbor route and its total distance. The function will take a list of strings cities and a list of lists dist_matrix that represents the distance matrix of the cities. Try every possible starting city, close each nearest neighbor route by returning to its start, and return a route with the smallest total distance among these candidates. Any tied best route is acceptable.

Tip: Use the find_nearest_neighbor function.

Function signature: find_best_nn_route(cities: list[str], dist_matrix: list[list[int]]) -> tuple[tuple[str, ...], int]

Parameters:

  • cities (list[str]): A list of strings representing the cities.
  • dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.

Returns:

  • tuple[tuple[str, ...], int]: A tuple of the best nearest neighbor route and its total distance.

Constraints:

  • The length of the cities will be at least 2.
  • The distance matrix will have a minimum size of 2x2.
  • The distance matrix will be symmetric.
  • The route will start and end at the same city.

Example:

Listing 4 shows a closed route and its total distance.

Listing 4: Return a nearest neighbor route and its total distance. 
cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

route, total_distance = find_best_nn_route(cities, dist_matrix)

print(route)  # Output: ('A', 'B', 'C', 'A')
print(total_distance)  # Output: 6

Alternative distance matrix representation (dictionary of dictionaries)

Re-do the exercises above using a dictionary of dictionaries to represent the distance matrix. The keys of the first-level dictionary will be the origin cities, and the values will be dictionaries with the destination cities as keys and the distances as values. Notice that when using dictionaries, the cities list does not need to be passed as a parameter. The adjusted function signatures are:

  • find_distance_between(origin: str, destination: str, dist_matrix: dict[str, dict[str, int]]) -> int
  • print_all_distances(dist_matrix: dict[str, dict[str, int]]) -> str
  • find_nearest_neighbor(route: tuple[str, ...], dist_matrix: dict[str, dict[str, int]]) -> str
  • find_best_nn_route(dist_matrix: dict[str, dict[str, int]]) -> tuple[tuple[str, ...], int]

Converting the distance matrix representation

Create a function that converts the list of lists representation of the distance matrix to the dictionary of dictionaries representation. The function will take a list of strings cities and a list of lists dist_matrix that represents the distance matrix of the cities. The function should return a dictionary of dictionaries that represents the distance matrix.

Function signature: convert_to_dict_of_dicts(cities: list[str], dist_matrix: list[list[int]]) -> dict[str, dict[str, int]]

Parameters:

  • cities (list[str]): A list of strings representing the cities.
  • dist_matrix (list[list[int]]): A list of lists representing the distance matrix of the cities.

Returns:

  • dict[str, dict[str, int]]: A dictionary of dictionaries that represents the distance matrix.

Constraints:

  • The length of the cities will be at least 2.
  • The distance matrix will have a minimum size of 2x2.
  • The distance matrix will be symmetric.
  • The cities will be unique.
  • The rows and columns of the distance matrix will be in the same order as the cities.
  • The distance matrix will have the same length as the cities.

Example:

Listing 5 shows the dictionary returned for three cities.

Listing 5: Convert a distance matrix to a dictionary of dictionaries. 
cities = ['A', 'B', 'C']

dist_matrix = [
    [0, 1, 2],
    [1, 0, 3],
    [2, 3, 0]
]

dist_matrix_dict = convert_to_dict_of_dicts(cities, dist_matrix)

print(dist_matrix_dict)  # Output: {'A': {'A': 0, 'B': 1, 'C': 2}, 'B': {'A': 1, 'B': 0, 'C': 3}, 'C': {'A': 2, 'B': 3, 'C': 0}}
  • cities.index(city) returns the zero-based position of the first matching name. The stated inputs guarantee that the name is present; otherwise it raises ValueError. For example, ["A", "B"].index("B") is 1.
  • len(values) returns its number of elements. range(n) supplies positions from 0 through n - 1. For example, list(range(len(["A", "B"]))) is [0, 1]. route[-1] selects the last item of a nonempty tuple.
  • route + (city,) returns a tuple with one city added at the end, leaving the original tuple unchanged. For example, ("A",) + ("B",) is ("A", "B").
  • dist_matrix[origin][destination] retrieves a dictionary’s distance value. Iterating over a dictionary visits its keys in insertion order. For example, with {"A": {"A": 0, "B": 1}}, the lookup for "A" and "B" returns 1.