Dijkstra算法解決了有向圖G=(V,E)上帶權的單源最短路徑問題，但要求所有邊的權值非負。
Dijkstra算法是貪婪算法的一個很好的例子。設置一頂點集合S，從源點s到集合中的頂點的最終最短路徑的權值均已確定。算法反復選擇具有最短路徑估計的頂點u，并將u加入到S中，對u
的所有出邊進行松弛。如果可以經(jīng)過u來改進到頂點v的最短路徑的話，就對頂點v的估計值進行更新。
如上圖，u為源點，頂點全加入到優(yōu)先隊列中。
，隊列中最小值為u(值為0)，u出隊列，對u的出邊進行松弛(x、v、w)，隊列最小值為x。
將x出列加入S，將x的出邊松弛(v、y、w)，其中w的值需要更新(4<5)，隊列最小值為v。
將v出列，加入到S中，將v的出邊松弛(w)，因x已在S中，故不做松弛。隊列中的最小值為y。
將y出列，y加入到S，松弛y的出邊(w、z)，更新w的值(3<4)，隊列最小值為w。
將w出列，加入到S中，松弛w的出邊(z)，隊列最小值為z。
將z出列，加入到S中。將z的出邊松弛(無)，此時隊列為空，算法結束。
Dijkstra算法的運行時間依賴于最小優(yōu)先隊列的具體實現(xiàn)。如果簡單的運用數(shù)組實現(xiàn)求最小值，運行時間為O(V2+E)=O(V2)。
如果圖比較稀疏，E=o(V2/lgV)，如果用二叉最小堆實現(xiàn)，則為O((V+E)lgV)。
如果用斐波那契堆實現(xiàn)，可以提升到O(VlgV+E)。
import sysclass Vertex(object): def __init__(self,key): self.id=key self.adj={} def addNeighbor(self,nbr,weight=0): self.adj[nbr]=weight def getNeighbors(self): return self.adj.keys() def getId(self): return self.id def getWeight(self,key): return self.adj[key]class Graph(object): def __init__(self): self.vertexlist={} self.size=0 def addVertex(self,key): vertex=Vertex(key) self.vertexlist[key]=vertex self.size+=1 return vertex def getVertex(self,key): return self.vertexlist.get(key) def __contains__(self,key): if key in self.vertexlist: return True else: return False def addEdge(self,f,t,weight=0): if f not in self.vertexlist: self.addVertex(f) if t not in self.vertexlist: self.addVertex(t) self.vertexlist[f].addNeighbor(self.vertexlist[t],weight) def getVertices(self): return self.vertexlist.keys() def __iter__(self): return iter(self.vertexlist.values())def Dijkstra(G,s): path={} vertexlist=[] for v in G: vertexlist.append(v) path[v]=sys.maxsize path[s]=0 queue=PRiorityQueue(path) queue.buildHeap(vertexlist) while queue.size>0: vertex=queue.delMin() for v in vertex.getNeighbors(): newpath=path[vertex]+vertex.getWeight(v) if newpath<path[v]: path[v]=newpath queue.perUp(v) return path class PriorityQueue(object): def __init__(self,path): self.path=path self.queue=[] self.size=0 def buildHeap(self,alist): self.queue=alist self.size=len(alist) for i in xrange(self.size/2-1,0,-1): self._perDown(i) def delMin(self): self.queue[0],self.queue[-1]=self.queue[-1],self.queue[0] minvertex=self.queue.pop() self.size-=1 self._perDown(0) return minvertex def perUp(self,v): i=self.queue.index(v) self._perUp(i) def _perUp(self,i): if i>0: if self.path[self.queue[i]]<=self.path[self.queue[(i-1)/2]]: self.queue[i],self.queue[(i-1)/2]=self.queue[(i-1)/2],self.queue[i] self._perUp((i-1)/2) def _perDown(self,i): left=2*i+1 right=2*i+2 little=i if left<=self.size-1 and self.path[self.queue[left]]<=self.path[self.queue[i]]: little=left if right<=self.size-1 and self.path[self.queue[right]]<=self.path[self.queue[little]]: little=right if little!=i: self.queue[i],self.queue[little]=self.queue[little],self.queue[i] self._perDown(little) if __name__=='__main__': g= Graph() g.addEdge('u','x',1) g.addEdge('u','v',2) g.addEdge('u','w',5) g.addEdge('x','v',2) g.addEdge('x','y',1) g.addEdge('x','w',3) g.addEdge('v','w',3) g.addEdge('y','w',1) g.addEdge('y','z',1) g.addEdge('w','z',5) u=g.getVertex('u') path=Dijkstra(g,u) for v in path: print v.id,path[v]
新聞熱點
疑難解答
