Traveling Salesperson

I’ve completed my code for the ‘Traveling Salesperson’ project on the Python CS career path, but my code doesn’t seem to be working and I have no clue what is going on.
Can I get some help?

There are three files used in this project:

  • script.py
  • Vertex.py
  • Graph.py

script.py

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) 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 = {vertex:'unvisited' for vertex 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)

Vertex.py

class Vertex: def __init__(self, value): self.value = value self.edges = {} def add_edge(self, vertex, weight=0): self.edges[vertex] = weight def get_edges(self): return list(self.edges.keys()) def get_edge_weight(self, edge): return self.edges[edge]

Graph.py

class Graph: def __init__(self, directed=False): self.graph_dict = {} self.directed = directed def add_vertex(self, vertex): self.graph_dict[vertex.value] = vertex def add_edge(self, from_vertex, to_vertex, weight=0): self.graph_dict[from_vertex.value].add_edge(to_vertex.value, weight) if not self.directed: self.graph_dict[to_vertex.value].add_edge(from_vertex.value, weight) def find_path(self, start_vertex, end_vertex): start = [start_vertex] seen = {} while len(start) > 0: current_vertex = start.pop(0) seen[current_vertex] = True print("Visiting " + current_vertex) if current_vertex == end_vertex: return True else: vertices_to_visit = set(self.graph_dict[current_vertex].edges.keys()) start += [vertex for vertex in vertices_to_visit if vertex not in seen] return False

Thanks for the help.

There are limitations with Codebyte when sharing one’s code. None of the code runs above b/c you can’t import Python libraries. If you want to share your code/ask a question about debugging it, then share your GitHub repo link so people can see the code there instead.

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.