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_Mod elling\Lab4\Lab _Transportation \shayslab4.py", line 104, in <module>
path1, dist1 = dijkstra_epp.sh ortestPath(newl ist, 'JuncID1027', 'n')
File "K:\Spatial_Mod elling\Lab4\Lab _Transportation \dijkstra_epp.p y", line 80, in shortestPath
D,P = Dijkstra(G,star t,end)
File "K:\Spatial_Mod elling\Lab4\Lab _Transportation \dijkstra_epp.p y", 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/insights/877227-dijkstras-algorithm-finding-shortest-route