-
Notifications
You must be signed in to change notification settings - Fork 0
/
traveling salesperson working
78 lines (72 loc) · 2.56 KB
/
traveling salesperson working
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import random
from random import randrange
from Graph import Graph
from Vertex import Vertex
def print_graph(graph):
for vertex in graph.graph_dict:
print("")
print(vertex + " connected to")
vertex_neighbors = graph.graph_dict[vertex].edges
if len(vertex_neighbors) == 0:
print("No edges!")
for adjacent_vertex in vertex_neighbors:
print("=> " + adjacent_vertex)
def build_tsp_graph(directed):
g = Graph(directed)
vertices = []
for val in ['a', 'b', 'c', 'd']:
vertex = Vertex(val)
vertices.append(vertex)
g.add_vertex(vertex)
g.add_edge(vertices[0], vertices[1], 3)
g.add_edge(vertices[0], vertices[2], 4)
g.add_edge(vertices[0], vertices[3], 5)
g.add_edge(vertices[1], vertices[0], 3)
g.add_edge(vertices[1], vertices[2], 2)
g.add_edge(vertices[1], vertices[3], 6)
g.add_edge(vertices[2], vertices[0], 4)
g.add_edge(vertices[2], vertices[1], 2)
g.add_edge(vertices[2], vertices[3], 1)
g.add_edge(vertices[3], vertices[0], 5)
g.add_edge(vertices[3], vertices[1], 6)
g.add_edge(vertices[3], vertices[2], 1)
# print_graph(g)
return g
# Define your functions below:
def visited_all_nodes(visited_vertices):
for vertex in visited_vertices:
if visited_vertices[vertex] == "unvisited":
return False
return True
def traveling_salesperson(graph):
ts_path=""
visited_vertices = {x: "unvisited" for x in graph.graph_dict}
current_vertex = random.choice(list(graph.graph_dict))
visited_vertices[current_vertex] = "visited"
ts_path += current_vertex
visited_all_vertices = visited_all_nodes(visited_vertices)
while not visited_all_vertices:
current_vertex_edges = graph.graph_dict[current_vertex].get_edges()
current_vertex_edge_weights = {}
for edge in current_vertex_edges:
current_vertex_edge_weights[edge] = graph.graph_dict[current_vertex].get_edge_weight(edge)
found_next_vertex = False
next_vertex = ""
while not found_next_vertex:
if current_vertex_edge_weights is None:
break
next_vertex = min(current_vertex_edge_weights, key=current_vertex_edge_weights.get)
if visited_vertices[next_vertex] == "visited":
current_vertex_edge_weights.pop(next_vertex)
else:
found_next_vertex = True
if current_vertex_edge_weights is None:
visited_all_vertices = True
else:
current_vertex = next_vertex
visited_vertices[current_vertex] = "visited"
ts_path += current_vertex
visited_all_vertices = visited_all_nodes(visited_vertices)
print(ts_path)
graph = build_tsp_graph(False)
traveling_salesperson(graph)