Please help me, I’m really desperate and I don’t know what to do.
So we had that assignment in university to program dijkstra’s algorithm in python.
INVALID_NODE = -1 #Define the initial variables to -1 and a very high number.
INFINITY = 1000000
#A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6
#network[0][1] is the cell that contains edge value for going from A to B
class Node:
previous = INVALID_NODE #With each node created, define it's initial variables to -1 and a very high number.
distFromSource = INFINITY
visited = False #Every node except starting node should be univisited by default.
def populateNetwork(filename):
network = [] #Create an empty array to store the network file.
networkfile = open(filename, "r") #Open the network file.
for line in networkfile: #For every line in network file, remove n's and split the data on every comma, then add everything to the array.
line = line.replace("n","")
line = line.split(',')
line = map(int, line)
network.append(line)
return network
def populateNodeTable(network, startNode): #Populate the nodeTable with node objects based on the network file.
nodeTable = []
for node in network:
nodeTable.append(Node())
nodeTable[startNode].distFromSource = 0 #Initialize the startNode distance from source and mark it as visited.
nodeTable[startNode].visited = True
return nodeTable
def findNeighbours(network, nodeTable, currentNode): #Function to find neighbours of the currentNode.
nearestNeighbour = [] #Empty array to store neighbour indexes.
columnIndex = 0
for entry in network[currentNode]: #check each node if it has a link to the currentNode and if it's unvisited, if both are true, add to the array.
if entry != 0 and nodeTable[columnIndex].visited == False:
nearestNeighbour.append(columnIndex)
columnIndex += 1
return nearestNeighbour
def calculateTentative(network, nodeTable, currentNode, nearestNeighbours):
#Calculate the distance from currentNode to each node in neighborous list
#Work out distance from source for each node
#If lower than current entry in nodeTable for that node, update
for neighbour in nearestNeighbours:
tentativeDistance = nodeTable[currentNode].distFromSource + network[currentNode][neighbour]
if nodeTable[neighbour].distFromSource > tentativeDistance:
nodeTable[neighbour].distFromSource = tentativeDistance
nodeTable[neighbour].previous = currentNode
return nodeTable
def findNextNode(nodeTable): #Find the next node from the neighbouring nodes with the lowest distFromSource.
currentDistance = INFINITY
nodeIndex = 0
currentNode = INVALID_NODE
for node in nodeTable: #If it's distFromSource is less than distFromSource of the currentNode, make it the currentNode.
if(node.distFromSource < currentDistance) and (node.visited == False):
currentNode = nodeIndex
currentDistance = node.distFromSource
nodeIndex += 1
return currentNode
####################
#Pseudocode from the internet for reference
#function Dijkstra(network, start):
# for each node v in network:
# distFromSource[v]:=infinity #initial distance from source to vertex v is set to infinite
# previous[v]:=undefined (-1) #previous node in optimal path from source
#
# distFromSource[source]:= 0 #distance from source to source
# Q:= the set of all nodes in Graph #all nodes in the graph are unoptimized - thus are in Q
#
# while Q is not empty: #main loop
# u:=node in Q with smallest dist[]
# remove u from Q
#
# for each neighbour v of u: #where v has not yet been removed from Q
# alt:=dist[u] + dist_between(u,v)
# if alt < dist[v]
# dist[v]:=alt #relax(u,v)
# previous[v]:=u
# return previous[]
#
####################
#Files
network = populateNetwork("network.txt") #Populate the network array with network defined in netwowrk.txt file.
routefile = "route.txt" #Load the route information.
letters = ["A", "B", "C", "D", "E",
"F", "G", "H", "I", "J", "K", "L", #Array of letters for easy conversion between integers and letters.
"M", "N", "O", "P", "Q", "R", "S",
"T", "U", "V", "W", "X", "Y", "Z"]
options = { "A": 0, "B": 1, #Dictionary to convert the initial route file to integers for much easier manipulation
"C": 2, "D": 3, #within the program.
"E": 4, "F": 5,
"G": 6, "H": 7,
"I": 8, "J": 9,
"K": 10, "L": 11,
"M": 12, "N": 13,
"O": 14, "P": 15,
"Q": 16, "R": 17,
"S": 18, "T": 19,
"U": 20, "V": 21,
"W": 22, "X": 23,
"Y": 24, "Z": 25,
}
####################
#Initial data and initialisation
print("Network file:") #Print the entire network.txt file to the screen line by line.
itr = 0 #Iterator for line labeling.
for line in network:
print(letters[itr], ".", line) #Prints letters associated with each node.
itr = itr + 1
with open(routefile, "r") as rfile: #Open route.txt and split it into two variables.
routeData = rfile.read().split(">")
routeData[0] = routeData[0].rstrip("n") #Strip route data from additional n's that can occur at the end of the file.
routeData[1] = routeData[1].rstrip("n")
startNode = options[routeData[0]] #Save both numbers as start and end nodes.
endNode = options[routeData[1]]
print("nRoute:n%s to %sn" %(letters[startNode], letters[endNode])) #Print start and end nodes to the user to make sure that
#the file was loaded correctly.
#Populate node table with the network data and starting node.
currentNode = startNode #Initialize currentNode to the start node.
print("Starting node: %snDestination node: %s" %(network[startNode], network[endNode])) #Prints the starting and end nodes.
####################
nodeTable = populateNodeTable(network, currentNode) #Populates nodeTable with node objects from the network.
while currentNode is not endNode: #While loop running as long as the currentNode isn't the destination.
neighbours = findNeighbours(network, nodeTable, currentNode) #Examine neighbours of the currentNode.
nodeTable = calculateTentative(network, nodeTable, currentNode, neighbours) #Calculate tentative distances for the neighbours of the currentNode.
nodeTable[currentNode].visited = True #Mark current node as visited.
currentNode = findNextNode(nodeTable) #Jump to the next neighbour.
#print "nChecking node: " #Print node the program is currently working on.
#print letters[currentNode]
####################
#New variable for the while loop.
routeList = [] #Array to store final route data.
routeList.append(letters[currentNode]) #Add the final node to the array.
while currentNode is not startNode: #Add all the nodes used in the final travel to the array using the nodetable[i].previous variable.
routeList.append(letters[nodeTable[currentNode].previous])
currentNode = nodeTable[currentNode].previous
print("nShortest route between start and end nodes: ")
for entry in reversed(routeList): #Print the array backwards for more intuitive output.
print(entry,)
print("nnTotal distance traveled:",) #Print the total distance traveled.
print(nodeTable[endNode].distFromSource)
####################
#Utility
print("n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~") #separator line for easier debugging
I did it on my laptop (it’s running debian) and it worked perfectly fine, the script is doing what it’s supposed to do and gives me the correct output.
When I run it, it says:
TypeError: 'map' object is not subscriptable
But here’s the problem: I got it due in 3 hours and I was going to upload it now, and I tried running it on my desktop pc (windows 10) just to make sure that I got the correct file.
But it’s acting up and it spits out an error I have absolutely no idea what it is because I’m just a beginner to python and this is my first term working with it…
Please help me! I’m trying to figure out why is it not working on windows but it’s beyond my knowledge.
It works 100% fine on linux though…
Please help me, I really don’t want to fail the module even though I did all the work…
Advertisement
Answer
- line = map(int, line) # in Python 3+ you will get the map object <map object at 0x.....> + line = list(map(int, line))