27  Route Finder App (NN Algorithm)

The nearest neighbor (NN) algorithm is a simple algorithm that is used to find the shortest path between a set of cities. 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 assignment, you will develop a route finder app that finds the best nearest neighbor route and its total distance using the NN algorithm.

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

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

27.1 Exercises

27.1.1 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 this link and use it in the exercises.

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.

27.1.2 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:

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

27.1.3 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:

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'

27.1.4 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 length of the route will be the same as the length of the distance matrix.
  • The nearest neighbor cannot be in the route.
  • The distance matrix will have a minimum size of 2x2.

Example:

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'

27.1.5 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. The function should return a tuple of the best nearest neighbor route and its total distance.

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.
  • route (tuple[str]): A tuple of strings representing the route.

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:

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

27.1.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]

27.1.7 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:

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}}