Dijkstra的Algoithm

我在使用Dijkstra的算法计算从最喜欢的点到某些交叉口的路径和距离时遇到了问题。这是我的代码:

选择 | 换行 | 行号
  1. import dijkstra_epp
  2.  
  3. file_loc = 'join_intersect.txt'
  4.  
  5. # create the file handle
  6. file = open(file_loc, 'r')
  7.  
  8. # put all lines from file in a list
  9. lines = file.readlines()
  10.  
  11. # dump/pop the header row
  12. header = lines.pop(0)
  13.  
  14. tokenlist = []              # initialize new list
  15.  
  16. # tokenizing the list
  17. for n in lines:
  18.     newline = n.split('\t')
  19.     tokenlist.append(newline)
  20.  
  21. # cleaning up the number element
  22. for n in tokenlist:
  23.     n[2] = float(n[2])
  24.  
  25. # extract edges and lengths from dataset
  26. edges = {}
  27.  
  28. # traverse the tokenlist and add edge weights to dict.
  29. for n in tokenlist:
  30.  
  31.     edge = n[1]
  32.     weight = n[2]
  33.  
  34.     if not edges.has_key(edge):
  35.         edges[edge] = weight    
  36.  
  37.  
  38. # Build adj. list structure for storing graph
  39. #
  40.  
  41.  
  42. # populate dictionary of edges
  43. edgList = {}
  44. for n in tokenlist:
  45.     if not edgList.has_key(n[0]):
  46.         edgList[n[1]] = []
  47. ##
  48.  
  49.  
  50. # determine which edges are associated with which nodes
  51. for n in tokenlist:
  52.     edgList[n[1]].append(n[0])
  53.  
  54.  
  55.  
  56. # populate shell of adjacency list
  57. adjList = {}
  58.  
  59. for n in edgList.keys():
  60.     nodes = edgList[n]
  61.     if not adjList.has_key(nodes[0]):
  62.         adjList[nodes[0]] = {}
  63.     if not adjList.has_key(nodes[1]):
  64.         adjList[nodes[1]] = {}
  65.  
  66. for n in edgList.keys():
  67.     nodes = edgList[n]
  68.  
  69.     adjList[nodes[0]][nodes[1]] = edges[n]
  70.     adjList[nodes[1]][nodes[0]] = edges[n]
  71.  
  72.  
  73. #
  74. # begin dijkstra
  75. #
  76.  
  77. path1, dist1 = dijkstra_epp.shortestPath(adjList, 'J2', 'J14')
  78.  
  79. #initializes a new list without my favorite place
  80.  
  81. newlist = [] 
  82.  
  83. # creates a new list that appends the adjList so that my favorite place is removed
  84.  
  85. for n in adjList:  
  86.     n != "JuncID1072"
  87.     newlist.append(adjList)
  88.  
  89. favoriteplace = []
  90.  
  91. for n in adjList:
  92.     n = "JuncID1072"
  93.     favoriteplace.append(adjList)
  94.  
  95. travelcosts = {}
  96. for n in newlist:
  97.  
  98.     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:列表索引必须是整数,而不是字符串

# 回答1



您没有显示您的图形类(我假设是G)。
但是有一个列表正在使用,您向它提供的是一个字符串而不是一个整数。
我敢打赌,Dijkstra_epp.py中G[v]中的v是一个字符串,而不是一个整数。
# 回答2


顺便说一句,我不久前实现了一个Dijkstra算法,并在这里写道:
Http://bytes.com/topic/python/insigh...shortest-route

标签: python

添加新评论