一个用来计算给定铁路线路图，对应两点所有路径的程序，用的深度优先回溯

railway_graph.py

# -*- coding: UTF-8 -*-
import sys, locale
import csv
import copy

reload(sys)
sys.setdefaultencoding('utf-8')


class Vertex(object):

	def __init__(self, name):
		self.name = name
	def __eq__(self, other):
		return self.name == other.name

	def __hash__(self):
		return hash(self.name)

	def __str__(self):
		return self.name

class Edge(object):

	def __init__(self, start_vertex, end_vertex, distance):
		self.start_vertex = start_vertex
		self.end_vertex = end_vertex
		self.distance = int(distance)

	def __eq__(self, other):
		return (self.start_vertex == other.start_vertex and self.end_vertex == other.end_vertex 
			and self.distance == other.distance)

	def __hash__(self):
		return hash(self.start_vertex) + hash(self.end_vertex) + self.distance

	def __str__(self):
		return str(self.start_vertex) + '_' + str(self.end_vertex) + ':' + str(self.distance)

class Result(object):

	def __init__(self):
		self.edges = []
		self.vertexs = []


def load_data():
	reader = csv.reader(open(unicode('线路.csv','utf8')))
	vertex_set = {}
	line1 = True
	for route_name, distance, start_station, dst_station, is_narrow_railway, note, number in reader:
		if line1:
			line1 = False
			continue
		# print unicode(start_station, 'utf-8'), unicode(dst_station, 'utf-8'), distance
		start_vertex = Vertex(unicode(start_station, 'utf-8'))
		end_vertex = Vertex(unicode(dst_station, 'utf-8'))
		edge = Edge(start_vertex, end_vertex, distance)
		edge_reverse = Edge(end_vertex, start_vertex, distance)
		if start_vertex not in vertex_set:
			vertex_set[start_vertex] = []
		if not edge in vertex_set[start_vertex]:
			vertex_set[start_vertex].append(edge)

		if end_vertex not in vertex_set:
			vertex_set[end_vertex] = []
		if not edge in vertex_set[end_vertex]:
			vertex_set[end_vertex].append(edge_reverse)

	return vertex_set

def log_vertex_set(vertex_set):
	for key in vertex_set:
		print_set_entry(key, vertex_set[key])

def print_set_entry(key, items):
	line = str(key) + ':['
	for item in items:
		line += str(item) + ','
	print unicode(line+ ']', 'utf-8')

def DFS(graph, start_vertex, end_vertex, results, path, vertexs, edge):
	vertexs.append(start_vertex)
	if edge:
		path.append(edge)
	if start_vertex == end_vertex:
		result = Result()
		result.edges = copy.deepcopy(path)
		result.vertexs = copy.deepcopy(vertexs)
		results.append(result)
		del vertexs[len(vertexs)-1]
		del path[len(path)-1]
		return
	for edge2 in graph[start_vertex]:
		if edge2.end_vertex not in vertexs:
			DFS(graph, edge2.end_vertex, end_vertex, results, path, vertexs, edge2)
	del vertexs[len(vertexs)-1]
	if edge:
		del path[len(path)-1]

def print_results(results):
	for result in results:
		distance = 0
		s = ''
		for edge in result.edges:
			distance += edge.distance
		for vertex in result.vertexs:
			s += str(vertex) + ','
		s = str(distance) + s
		print unicode(s, 'utf-8')

if __name__ == "__main__":
	vertex_set = load_data()
	log_vertex_set(vertex_set)
	while True:
		start_station = raw_input(u'输入起点名字（输入exit退出）:'.encode('gb18030'
			)).decode(sys.stdin.encoding or locale.getpreferredencoding(True))
		if start_station == 'exit':
			sys.exit(0)
		start_vertex = Vertex(unicode(str(start_station), 'utf-8'))
		if start_vertex in vertex_set:
			print_set_entry(start_vertex, vertex_set[start_vertex])

		end_station = raw_input(u'输入终点名字（输入exit退出，reset清除）:'.encode('gb18030'
			)).decode(sys.stdin.encoding or locale.getpreferredencoding(True))
		if end_station == 'exit':
			sys.exit(0)
		elif end_station == 'reset':
			continue
		end_vertex = Vertex(unicode(str(end_station), 'utf-8'))
		if end_vertex in vertex_set:
			print_set_entry(end_vertex, vertex_set[end_vertex])
		results = []
		path = []
		vertexs = []
		DFS(vertex_set, start_vertex, end_vertex, results, path, vertexs, None)
		print_results(results)

线路.csv