Dijkstra's Algoithm

[sdavis]

I Am having problems using Dijkstra's algorithm to calculate path and distance from a favorite point to certain junctions. This is my code:

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')

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

[Glenton]

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.

[Glenton]

Incidentally, I implemented a dijkstra algorithm some time back and wrote about it here:
http://bytes.com/topic/python/insigh...shortest-route