Create a Python program with functions using brute force, to find the routes between two cities (nodes), identifying the lowest and highest cost routes.

Implement lists, tuples, along with documentation itertools, using permutations.

Map 1

Map 2

1. Generate all possible routes -All nodes must be crossed (5 nodes) -Only crossing once for each node. -Non-directed networks, for example, route (5,4,3,2,1)

*** Show the total number of routes generated and show the routes

2. Calculate the cost of all valid routes that pass through the 5 nodes, for example (1,2,3,4,5) = $ 95

*** Show the total number of valid routes and show the routes with their cost.

*** Show the cost of the route with the lowest cost and show the routes with their cost.

*** Show the cost of the route with the highest cost and show the routes with their cost.

10 1 2 45 20 55 40 25 25 5 30 3 50 4 15 10 2 1 20 25 45 25 3 5 4 50 15 Input: Menu 1) Map 1 2) Map 2 Option: 1 Initial City: 4 Final City: 1 Output: Total routes: 120 ('1','2','3', '4', '5') ('1','2','3', '5', '4') ('1','2 4 '3', '5') 2 ('5', '4', ,'1','2') ('5','4 '3','2','1') Total valid routes: 12 ('1','2', '5','3', '4') = $95 ('4','3 '5 '2','1') = $95 ('1','2','3', '5', '4') = $110 2 ('1','3','2', '5', '4') = $165 ('4', '5','2 '3', '1') = $165 Lowest cost route: $95 ('1','2', '5','3', '4') = $95 ('4','3','5','2','1') = $95 Highest cost route: $165 ('1','3','2', '5', '4') $165 ('4', '5','2','3','1') $165