python中怎么利用Dijkstra算法求最短路徑

python中怎么利用Dijkstra算法求最短路徑，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

　　從某源點到其余各頂點的最短路徑

　　Dijkstra算法可用于求解圖中某源點到其余各頂點的最短路徑。假設G={V，{E｝｝是含有n個頂點的有向圖，以該圖中頂點v為源點，使用Dijkstra算法求頂點v到圖中其余各頂點的最短路徑的基本思想如下：

　　使用集合S記錄已求得最短路徑的終點，初始時S={v}。

　　選擇一條長度最小的最短路徑，該路徑的終點w屬于V-S，將w并入S，并將該最短路徑的長度記為Dw。

　　對于V-S中任一頂點是s，將源點到頂點s的最短路徑長度記為Ds，并將頂點w到頂點s的弧的權值記為Dws，若Dw+Dws

　　則將源點到頂點s的最短路徑長度修改為Dw+Ds=ws。

　　重復執行2和3，知道S=V。

　　為了實現算法，

　　使用鄰接矩陣Arcs存儲有向網，當i=j時，Arcs[i][j]=0;當i!=j時，若下標為i的頂點到下標為j的頂點有弧且弧的權值為w，則Arcs[i][j]=w，否則Arcs[i][j]=float(‘inf’)即無窮大。

　　使用Dist存儲源點到每一個終點的最短路徑長度。

　　使用列表Path存儲每一條最短路徑中倒數第二個頂點的下標。

　　使用flag記錄每一個頂點是否已經求得最短路徑，在思想中即是判斷頂點是屬于V集合，還是屬于V-S集合。

　　代碼實現

　　#構造有向圖Graph

　　class Graph:

　　def __init__(self,graph,labels): #labels為標點名稱

　　self.Arcs=graph

　　self.VertexNum=graph.shape[0]

　　self.labels=labels

　　def Dijkstra(self,Vertex,EndNode): #Vertex為源點，EndNode為終點

　　Dist=[[] for i in range(self.VertexNum)] #存儲源點到每一個終點的最短路徑的長度

　　Path=[[] for i in range(self.VertexNum)] #存儲每一條最短路徑中倒數第二個頂點的下標

　　flag=[[] for i in range(self.VertexNum)] #記錄每一個頂點是否求得最短路徑

　　index=0

　　#初始化

　　while index

　　Dist[index]=self.Arcs[Vertex][index]

　　flag[index]=0

　　if self.Arcs[Vertex][index]

　　Path[index]=Vertex

　　else:

　　Path[index]=-1 #表示從頂點Vertex到index無路徑

　　index+=1

　　flag[Vertex]=1

　　Path[Vertex]=0

　　Dist[Vertex]=0

　　index=1

　　while index

　　MinDist=float('inf')

　　j=0

　　while j

　　if flag[j]==0 and Dist[j]

　　tVertex=j #tVertex為目前從V-S集合中找出的距離源點Vertex最斷路徑的頂點

　　MinDist=Dist[j]

　　j+=1

　　flag[tVertex]=1

　　EndVertex=0

　　MinDist=float('inf') #表示無窮大，若兩點間的距離小于MinDist說明兩點間有路徑

　　#更新Dist列表，符合思想中第三條

　　while EndVertex

　　if flag[EndVertex]==0:

　　if self.Arcs[tVertex][EndVertex]

　　tVertex]+self.Arcs[tVertex][EndVertex]

　　Dist[EndVertex]=Dist[tVertex]+self.Arcs[tVertex][EndVertex]

　　Path[EndVertex]=tVertex

　　EndVertex+=1

　　index+=1

　　vertex_endnode_path=[] #存儲從源點到終點的最短路徑

　　return Dist[EndNode],start_end_Path(Path,Vertex,EndNode,vertex_endnode_path)

　　#根據本文上述定義的Path遞歸求路徑

　　def start_end_Path(Path,start,endnode,path):

　　if start==endnode:

　　path.append(start)

　　else:無錫婦科醫院哪家好 http://www.xasgfk.cn/

　　path.append(endnode)

　　start_end_Path(Path,start,Path[endnode],path)

　　return path

　　if __name__=='__main__':

　　#float('inf')表示無窮

　　graph=np.array([[0,6,5,float('inf'),float('inf'),float('inf')],

　　[float('inf'),0,2,8,float('inf'),float('inf')],

　　[float('inf'),float('inf'),0,float('inf'),3,float('inf')],

　　[float('inf'),float('inf'),7,0,float('inf'),9],

　　[float('inf'),float('inf'),float('inf'),float('inf'),0,9],

　　[float('inf'),float('inf'),float('inf'),float('inf'),0]])

　　G=Graph(graph,labels=['a','b','c','d','e','f'])

　　start=input('請輸入源點')

　　endnode=input('請輸入終點')

　　dist,path=Dijkstra(G,G.labels.index(start),G.labels.index(endnode))

　　Path=[]

　　for i in range(len(path)):

　　Path.append(G.labels[path[len(path)-1-i]])

　　print('從頂點{}到頂點{}的最短路徑為：\n{}\n最短路徑長度為：{}'.format(start,endnode,Path,dist))

　　輸出結果如下：

　　請輸入源點

　　a

　　請輸入終點

　　f

　　從頂點a到頂點f的最短路徑為：

　　['a', 'c', 'e', 'f']

　　最短路徑長度為：17

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。