北京地铁计费系统--python实现dijkstra算法

from tkinter import * import csv import re sta = '' end = '' dict1 = {} with open('weight.csv', 'r')as csv_file: data = csv.DictReader(csv_file, delimiter=",") for row in data: if row['now'] in dict1: dict2 = dict1[row['now']] dict2[row['next']] = row['distance'] dict1[row['now']] = dict2 else: dict2 = {} dict2[row['next']] = row['distance'] dict1[row['now']] = dict2 #拷贝dict1 name_list = [] dict_all = {} for key,value in dict1.items(): dict_all[key] = value #创建站名的列表 for key in dict1.keys(): name_list.append(key) #创建邻接矩阵 for i in range (len(name_list)): for j in range (len(name_list)): if i == j: dict_all[name_list[i]][name_list[j]] = 0 elif name_list[j] in dict_all[name_list[i]]: pass else: dict_all[name_list[i]][name_list[j]] = 10000000000 #到不了的点的距离 def dijkstra(name_list,W,s,e): fare.delete(0.0, END) s = name_list.index(s) #s在列表中的位置 MAX = 10000000000; distance = [MAX for x in range (len(name_list))] #初始化 distance[s] = 0 min_point = s T = set() #已经计算出最短距离的点 while (len(T) < len(name_list)): T.add(min_point) for lin_name,weight in W[name_list[min_point]].items(): lin = name_list.index(lin_name) weight = int(weight) if lin not in T : #更新不属于T的点 distance[lin] = min(distance[lin],distance[min_point]+int(W[name_list[min_point]][name_list[lin]])) min_distance = MAX for i,d in enumerate(distance): #选出不属于T的距离的最小值 if i not in T and d>0 and d<min_distance: min_distance = d; min_point = i; end_num = name_list.index(e) Length = distance[end_num] # print(distance[end_num]) if Length <= 6000: fare.insert('end',"3元") elif Length <= 12000: fare.insert('end',"4元") elif Length <= 22000: fare.insert('end',"5元") elif Length <= 32000: fare.insert('end',"6元") else: x = Length - 32000 money = int(6 + x / 20000 + 1) fare.insert('end',str(money)+ '元') return distance[end_num] def dijkstra1(): s=sta e=end dijkstra(name_list,dict_all,s,e) class AutocompleteEntry(Entry): def __init__(self, autocompleteList, *args, **kwargs): self.listboxLength = kwargs['listboxLength'] del kwargs['listboxLength'] self.matchesFunction = kwargs['matchesFunction'] del kwargs['matchesFunction'] self.matchesFunction = matches Entry.__init__(self, *args, **kwargs) self.focus() self.autocompleteList = autocompleteList self.var = self["textvariable"] if self.var == '': self.var = self["textvariable"] = StringVar() self.var.trace('w', self.changed) self.bind("<Return>", self.selection) self.bind("<Up>", self.moveUp) self.bind("<Down>", self.moveDown) self.listboxUp = False def changed(self, name, index, mode): if self.var.get() == '': if self.listboxUp: self.listbox.destroy() self.listboxUp = False else: words = self.comparison() if words: if not self.listboxUp: self.listbox = Listbox(width=self["width"], height=self.listboxLength) self.listbox.bind("<Right>", self.selection) self.listbox.place(x=self.winfo_x(), y=self.winfo_y() + self.winfo_height()) self.listboxUp = True self.listbox.delete(0, END) for word in words: self.listbox.insert(END, word) else: if self.listboxUp: self.listbox.destroy() self.listboxUp = False def selection(self, event): if self.listboxUp: self.var.set(self.listbox.get(ACTIVE)) self.listbox.destroy() self.listboxUp = False self.icursor(END) def moveUp(self, event): if self.listboxUp: if self.listbox.curselection() == (): index = '0' else: index = self.listbox.curselection()[0] if index != '0': self.listbox.selection_clear(first=index) index = str(int(index) - 1) self.listbox.see(index) self.listbox.selection_set(first=index) self.listbox.activate(index) def moveDown(self, event): if self.listboxUp: if self.listbox.curselection() == (): index = '0' else: index = self.listbox.curselection()[0] if index != END: self.listbox.selection_clear(first=index) index = str(int(index) + 1) self.listbox.see(index) # Scroll! self.listbox.selection_set(first=index) self.listbox.activate(index) def comparison(self): global sta sta = self.var.get() # print('sta:',sta) return [w for w in self.autocompleteList if self.matchesFunction(self.var.get(), w)] class AutocompleteEntry1(Entry): def __init__(self, autocompleteList, *args, **kwargs): self.listboxLength = kwargs['listboxLength'] del kwargs['listboxLength'] self.matchesFunction = kwargs['matchesFunction'] del kwargs['matchesFunction'] self.matchesFunction = matches Entry.__init__(self, *args, **kwargs) self.focus() self.autocompleteList = autocompleteList self.var = self["textvariable"] if self.var == '': self.var = self["textvariable"] = StringVar() self.var.trace('w', self.changed) self.bind("<Return>", self.selection) self.bind("<Up>", self.moveUp) self.bind("<Down>", self.moveDown) self.listboxUp = False def changed(self, name, index, mode): if self.var.get() == '': if self.listboxUp: self.listbox.destroy() self.listboxUp = False else: words = self.comparison() if words: if not self.listboxUp: self.listbox = Listbox(width=self["width"], height=self.listboxLength) self.listbox.bind("<Right>", self.selection) self.listbox.place(x=self.winfo_x(), y=self.winfo_y() + self.winfo_height()) self.listboxUp = True self.listbox.delete(0, END) for word in words: self.listbox.insert(END, word) else: if self.listboxUp: self.listbox.destroy() self.listboxUp = False def selection(self, event): if self.listboxUp: self.var.set(self.listbox.get(ACTIVE)) self.listbox.destroy() self.listboxUp = False self.icursor(END) def moveUp(self, event): if self.listboxUp: if self.listbox.curselection() == (): index = '0' else: index = self.listbox.curselection()[0] if index != '0': self.listbox.selection_clear(first=index) index = str(int(index) - 1) self.listbox.see(index) # Scroll! self.listbox.selection_set(first=index) s