By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,923 Members | 1,655 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,923 IT Pros & Developers. It's quick & easy.

Dijkstra's Algoithm

P: 1
I Am having problems using Dijkstra's algorithm to calculate path and distance from a favorite point to certain junctions. This is my code:
Expand|Select|Wrap|Line Numbers
  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')
This is the error: any ideas?

Traceback (most recent call last):
File "K:\Spatial_Modelling\Lab4\Lab_Transportation\shay slab4.py", line 104, in <module>
path1, dist1 = dijkstra_epp.shortestPath(newlist, 'JuncID1027', 'n')
File "K:\Spatial_Modelling\Lab4\Lab_Transportation\dijk stra_epp.py", line 80, in shortestPath
D,P = Dijkstra(G,start,end)
File "K:\Spatial_Modelling\Lab4\Lab_Transportation\dijk stra_epp.py", line 59, in Dijkstra
for w in G[v]:
TypeError: list indices must be integers, not str
Oct 30 '11 #1
Share this Question
Share on Google+
2 Replies


Expert 100+
P: 391
Hi

You're not showing your graph class (G, I assume).

But there's a list being used somewhere where you're feeding it a string instead of an integer.

I'd be willing to bet that it's the v in G[v] in dijkstra_epp.py that is a string instead of an integer.
Oct 31 '11 #2

Expert 100+
P: 391
Incidentally, I implemented a dijkstra algorithm some time back and wrote about it here:
http://bytes.com/topic/python/insigh...shortest-route
Oct 31 '11 #3

Post your reply

Sign in to post your reply or Sign up for a free account.