forked from petkofff/p_vs_np_challenge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
demo.py
50 lines (42 loc) · 1.71 KB
/
demo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
routes = []
def find_paths(node, cities, path, distance):
# Add way point
path.append(node)
# Calculate path length from current to last node
if len(path) > 1:
distance += cities[path[-2]][node]
# If path contains all cities and is not a dead end,
# add path from last to first city and return.
if (len(cities) == len(path)) and (path[0] in cities[path[-1]]):
global routes
path.append(path[0])
distance += cities[path[-2]][path[0]]
print(path, distance)
routes.append([distance, path])
return
# Fork paths for all possible cities not yet used
for city in cities:
if (city not in path) and (node in cities[city]):
find_paths(city, dict(cities), list(path), distance)
#CHALLENGE -- write your own strategy to estimate the shortest route
#def find_paths_estimate(node, cities, path, distance):
if __name__ == '__main__':
cities = {
'RV': {'S': 195, 'UL': 86, 'M': 178, 'BA': 180, 'Z': 91},
'UL': {'RV': 86, 'S': 107, 'N': 171, 'M': 123},
'M': {'RV': 178, 'UL': 123, 'N': 170},
'S': {'RV': 195, 'UL': 107, 'N': 210, 'F': 210, 'MA': 135, 'KA': 64},
'N': {'S': 210, 'UL': 171, 'M': 170, 'MA': 230, 'F': 230},
'F': {'N': 230, 'S': 210, 'MA': 85},
'MA': {'F': 85, 'N': 230, 'S': 135, 'KA': 67},
'KA': {'MA': 67, 'S': 64, 'BA': 191},
'BA': {'KA': 191, 'RV': 180, 'Z': 85, 'BE': 91},
'BE': {'BA': 91, 'Z': 120},
'Z': {'BA': 120, 'BE': 85, 'RV': 91}
}
print("Brute force algorithm:")
print("Start: River City")
find_paths('RV', cities, [], 0)
routes.sort()
if len(routes) != 0:
print("Shortest route: %s" % routes[0])