欧美成人午夜免费全部完,亚洲午夜福利精品久久,а√最新版在线天堂,另类亚洲综合区图片小说区,亚洲欧美日韩精品色xxx

千鋒扣丁學(xué)堂Python培訓(xùn)之Dijkstra算法實(shí)現(xiàn)最短路徑問題方法

2019-09-19 13:07:02 5045瀏覽

今天千鋒扣丁學(xué)堂Python培訓(xùn)老師給大家分享一篇關(guān)于Dijkstra算法實(shí)現(xiàn)最短路徑問題的方法的詳細(xì)介紹，文中通過示例代碼介紹的非常詳細(xì)，下面我們一起來看一下吧。


從某源點(diǎn)到其余各頂點(diǎn)的最短路徑

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

使用集合S記錄已求得最短路徑的終點(diǎn)，初始時(shí)S={v}。

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

對(duì)于V-S中任一頂點(diǎn)是s，將源點(diǎn)到頂點(diǎn)s的最短路徑長度記為Ds，并將頂點(diǎn)w到頂點(diǎn)s的弧的權(quán)值記為Dws，若Dw+Dws<Ds，

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

重復(fù)執(zhí)行2和3，知道S=V。

為了實(shí)現(xiàn)算法，

使用鄰接矩陣Arcs存儲(chǔ)有向網(wǎng)，當(dāng)i=j時(shí)，Arcs[i][j]=0；當(dāng)i!=j時(shí)，若下標(biāo)為i的頂點(diǎn)到下標(biāo)為j的頂點(diǎn)有弧且弧的權(quán)值為w，則Arcs[i][j]=w，否則Arcs[i][j]=float(‘inf')即無窮大。

使用Dist存儲(chǔ)源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長度。

使用列表Path存儲(chǔ)每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)。

使用flag記錄每一個(gè)頂點(diǎn)是否已經(jīng)求得最短路徑，在思想中即是判斷頂點(diǎn)是屬于V集合，還是屬于V-S集合。

代碼實(shí)現(xiàn)

#構(gòu)造有向圖Graph
class Graph:
  def __init__(self,graph,labels): #labels為標(biāo)點(diǎn)名稱
    self.Arcs=graph
    self.VertexNum=graph.shape[0]
    self.labels=labels
def Dijkstra(self,Vertex,EndNode): #Vertex為源點(diǎn)，EndNode為終點(diǎn)
  Dist=[[] for i in range(self.VertexNum)] #存儲(chǔ)源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑的長度
  Path=[[] for i in range(self.VertexNum)] #存儲(chǔ)每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)
  flag=[[] for i in range(self.VertexNum)] #記錄每一個(gè)頂點(diǎn)是否求得最短路徑
  index=0
  #初始化
  while index<self.VertexNum:
    Dist[index]=self.Arcs[Vertex][index]
    flag[index]=0
    if self.Arcs[Vertex][index]<float('inf'): #正無窮
      Path[index]=Vertex
    else:
      Path[index]=-1 #表示從頂點(diǎn)Vertex到index無路徑
    index+=1
  flag[Vertex]=1
  Path[Vertex]=0
  Dist[Vertex]=0
  index=1
  while index<self.VertexNum:
    MinDist=float('inf')
    j=0
    while j<self.VertexNum:
      if flag[j]==0 and Dist[j]<MinDist:
        tVertex=j #tVertex為目前從V-S集合中找出的距離源點(diǎn)Vertex最斷路徑的頂點(diǎn)
        MinDist=Dist[j]
      j+=1
    flag[tVertex]=1
    EndVertex=0
    MinDist=float('inf') #表示無窮大，若兩點(diǎn)間的距離小于MinDist說明兩點(diǎn)間有路徑
    #更新Dist列表，符合思想中第三條
    while EndVertex<self.VertexNum:
      if flag[EndVertex]==0:
        if self.Arcs[tVertex][EndVertex]<MinDist and Dist[
          tVertex]+self.Arcs[tVertex][EndVertex]<Dist[EndVertex]:
          Dist[EndVertex]=Dist[tVertex]+self.Arcs[tVertex][EndVertex]
          Path[EndVertex]=tVertex
      EndVertex+=1
    index+=1
  vertex_endnode_path=[] #存儲(chǔ)從源點(diǎn)到終點(diǎn)的最短路徑
  return Dist[EndNode],start_end_Path(Path,Vertex,EndNode,vertex_endnode_path)
#根據(jù)本文上述定義的Path遞歸求路徑
def start_end_Path(Path,start,endnode,path):
  if start==endnode:
    path.append(start)
  else:
    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('請(qǐng)輸入源點(diǎn)')
  endnode=input('請(qǐng)輸入終點(diǎn)')
  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('從頂點(diǎn){}到頂點(diǎn){}的最短路徑為：\n{}\n最短路徑長度為：{}'.format(start,endnode,Path,dist))

輸出結(jié)果如下：

請(qǐng)輸入源點(diǎn)
a
請(qǐng)輸入終點(diǎn)
f
從頂點(diǎn)a到頂點(diǎn)f的最短路徑為：
['a', 'c', 'e', 'f']
最短路徑長度為：17

以上就是關(guān)于千鋒扣丁學(xué)堂Python培訓(xùn)之Dijkstra算法實(shí)現(xiàn)最短路徑問題方法全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，想要了解更多關(guān)于Python和人工智能方面內(nèi)容的小伙伴，請(qǐng)關(guān)注扣丁學(xué)堂Python培訓(xùn)官網(wǎng)、微信等平臺(tái)，扣丁學(xué)堂IT職業(yè)在線學(xué)習(xí)教育平臺(tái)為您提供權(quán)威的Python開發(fā)環(huán)境搭建視頻，Python培訓(xùn)后的前景無限，行業(yè)薪資和未來的發(fā)展會(huì)越來越好的，扣丁學(xué)堂老師精心推出的Python視頻教程定能讓你快速掌握Python從入門到精通開發(fā)實(shí)戰(zhàn)技能?？鄱W(xué)堂Python技術(shù)交流群：279521237。

                          

      【關(guān)注微信公眾號(hào)獲取更多學(xué)習(xí)資料】         【掃碼進(jìn)入Python全棧開發(fā)免費(fèi)公開課】

查看更多關(guān)于"Python開發(fā)資訊"的相關(guān)文章>