Dijkstra的Algoithm
我在使用Dijkstra的算法计算从最喜欢的点到某些交叉口的路径和距离时遇到了问题。这是我的代码:
选择 | 换行 | 行号
- import dijkstra_epp
- file_loc = 'join_intersect.txt'
- # create the file handle
- file = open(file_loc, 'r')
- # put all lines from file in a list
- lines = file.readlines()
- # dump/pop the header row
- header = lines.pop(0)
- tokenlist = [] # initialize new list
- # tokenizing the list
- for n in lines:
- newline = n.split('\t')
- tokenlist.append(newline)
- # cleaning up the number element
- for n in tokenlist:
- n[2] = float(n[2])
- # extract edges and lengths from dataset
- edges = {}
- # traverse the tokenlist and add edge weights to dict.
- for n in tokenlist:
- edge = n[1]
- weight = n[2]
- if not edges.has_key(edge):
- edges[edge] = weight
- # Build adj. list structure for storing graph
- #
- # populate dictionary of edges
- edgList = {}
- for n in tokenlist:
- if not edgList.has_key(n[0]):
- edgList[n[1]] = []
- ##
- # determine which edges are associated with which nodes
- for n in tokenlist:
- edgList[n[1]].append(n[0])
- # populate shell of adjacency list
- adjList = {}
- for n in edgList.keys():
- nodes = edgList[n]
- if not adjList.has_key(nodes[0]):
- adjList[nodes[0]] = {}
- if not adjList.has_key(nodes[1]):
- adjList[nodes[1]] = {}
- for n in edgList.keys():
- nodes = edgList[n]
- adjList[nodes[0]][nodes[1]] = edges[n]
- adjList[nodes[1]][nodes[0]] = edges[n]
- #
- # begin dijkstra
- #
- path1, dist1 = dijkstra_epp.shortestPath(adjList, 'J2', 'J14')
- #initializes a new list without my favorite place
- newlist = []
- # creates a new list that appends the adjList so that my favorite place is removed
- for n in adjList:
- n != "JuncID1072"
- newlist.append(adjList)
- favoriteplace = []
- for n in adjList:
- n = "JuncID1072"
- favoriteplace.append(adjList)
- travelcosts = {}
- for n in newlist:
- path1, dist1 = dijkstra_epp.shortestPath(newlist, 'JuncID1027', 'n')
这就是错误:有什么想法吗?
回溯(最近一次呼叫):
文件"K:\Spatial_Modelling\Lab4\Lab_Transportation\shay slab4.py",第104行,in
路径1,Dist1=Dijkstra_epp.ShorestPath(newlist,'JuncID1027','n')
文件"K:\Spatial_Modelling\Lab4\Lab_Transportation\dijk stra_epp.py",第80行,在最短路径中
D,P=Dijkstra(G,开始,结束)
文件"K:\Spatial_Modelling\Lab4\Lab_Transportation\dijk stra_epp.py",第59行,Dijkstra
对于G[v]中的w:
TypeError:列表索引必须是整数,而不是字符串