0
我有使用鄰接列表的圖的實現,我想使它與Dijkstra的算法一起工作。我不知道自己是否腦死亡,但我想不出讓優先隊列版本找到從源到最短的最短路徑。我已經閱讀了維基百科頁面,但這還不夠。任何人都可以幫忙嗎?!在Python中使用優先隊列在Dijkstra算法上尋找目標節點
class Vertex:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
def getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self,n):
return n in self.vertList
def addEdge(self,f,t,cost=0):
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
def main(self, input1):
"""
Automates the insertion process
"""
try:
if input1 is None:
ans=True
while ans != False:
print ("""
1.Insert nodes
2.Print representation
3.Exit
""")
ans=input("What would you like to do?")
if ans=="1":
rfilename = input("Enter file to read: ")
f = open(rfilename) #file 1
linelist = list(f) #linelist is a list with each member corresponding to one line in the txt file
for i in range(len(linelist)): #inserts all vertexes
line = linelist[i].split()
self.addVertex(line[0])
for i in range(len(linelist)): #inserts all edges
line = linelist[i].split()
self.addEdge(line[0], line[1], int(line[2]))
elif ans=="2":
for v in self:
for w in v.getConnections():
print("(%s to %s, %s)" % (v.getId(), w.getId(), v.getWeight(w)))
elif ans=="3":
ans = False
except(FileNotFoundError):
print("File not found")
def dijkstra(self,start):
pq = PriorityQueue()
start.setDistance(0)
pq.insert([(v.getDistance(),v) for v in self])
while not pq.is_empty():
currentVert = pq.remove()
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance() + currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance(newDist)
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert,newDist)
我怎麼能改變這個包括停在目標? – veronik 2014-09-23 14:01:06