欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python Dijkstra算法實現(xiàn)最短路徑問題的方法

 更新時間:2019年09月19日 10:25:07   作者:會飛的哼哧  
這篇文章主要介紹了python Dijkstra算法實現(xiàn)最短路徑問題的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

本文借鑒于張廣河教授主編的《數(shù)據結構》,對其中的代碼進行了完善。

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

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<Ds,
  • 則將源點到頂點s的最短路徑長度修改為Dw+Ds=ws。
  • 重復執(zhí)行2和3,知道S=V。
  • 為了實現(xiàn)算法,
  • 使用鄰接矩陣Arcs存儲有向網,當i=j時,Arcs[i][j]=0;當i!=j時,若下標為i的頂點到下標為j的頂點有弧且弧的權值為w,則Arcs[i][j]=w,否則Arcs[i][j]=float(‘inf')即無窮大。
  • 使用Dist存儲源點到每一個終點的最短路徑長度。
  • 使用列表Path存儲每一條最短路徑中倒數(shù)第二個頂點的下標。
  • 使用flag記錄每一個頂點是否已經求得最短路徑,在思想中即是判斷頂點是屬于V集合,還是屬于V-S集合。

代碼實現(xiàn)

#構造有向圖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)] #存儲每一條最短路徑中倒數(shù)第二個頂點的下標
  flag=[[] for i in range(self.VertexNum)] #記錄每一個頂點是否求得最短路徑
  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 #表示從頂點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集合中找出的距離源點Vertex最斷路徑的頂點
        MinDist=Dist[j]
      j+=1
    flag[tVertex]=1
    EndVertex=0
    MinDist=float('inf') #表示無窮大,若兩點間的距離小于MinDist說明兩點間有路徑
    #更新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=[] #存儲從源點到終點的最短路徑
  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:
    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

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關文章

  • Python中的random函數(shù)實例詳解

    Python中的random函數(shù)實例詳解

    random模塊提供生成偽隨機數(shù)的函數(shù),在使用時需要導入random模塊,這篇文章主要介紹了Python中的random函數(shù),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-02-02
  • 淺談Python2之漢字編碼為unicode的問題(即類似\xc3\xa4)

    淺談Python2之漢字編碼為unicode的問題(即類似\xc3\xa4)

    今天小編就為大家分享一篇淺談Python2之漢字編碼為unicode的問題(即類似\xc3\xa4),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-08-08
  • python中列表推導式與生成器表達式對比詳解

    python中列表推導式與生成器表達式對比詳解

    python當然不是一門編譯型語言,但是它還是要被解析成二進制的字節(jié)碼才能被執(zhí)行,執(zhí)行它的正是python解釋器,下面這篇文章主要給大家介紹了關于python中列表推導式與生成器表達式對比的相關資料,需要的朋友可以參考下
    2023-01-01
  • python+django+rest框架配置創(chuàng)建方法

    python+django+rest框架配置創(chuàng)建方法

    今天小編就為大家分享一篇python+django+rest框架配置創(chuàng)建方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-08-08
  • Python全棧之學習MySQL(2)

    Python全棧之學習MySQL(2)

    這篇文章主要為大家介紹了Python全棧之MySQL,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-01-01
  • PyTorch基本數(shù)據類型(一)

    PyTorch基本數(shù)據類型(一)

    這篇文章主要為大家詳細介紹了PyTorch基本數(shù)據類型,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-05-05
  • BeautifulSoup獲取指定class樣式的div的實現(xiàn)

    BeautifulSoup獲取指定class樣式的div的實現(xiàn)

    這篇文章主要介紹了BeautifulSoup獲取指定class樣式的div的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • python利用xpath爬取網上數(shù)據并存儲到django模型中

    python利用xpath爬取網上數(shù)據并存儲到django模型中

    這篇文章主要介紹了python利用xpath爬取網上數(shù)據并存儲到django模型中,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-02-02
  • Python學習之包與模塊詳解

    Python學習之包與模塊詳解

    在了解完面向對象與異常處理機制之后,本文將詳細為大家介紹Python中的包與模塊,文中的示例講解詳細,感興趣的小伙伴可以學習一下
    2022-03-03
  • Python+PyQt5實現(xiàn)開發(fā)Memcached客戶端

    Python+PyQt5實現(xiàn)開發(fā)Memcached客戶端

    這篇文章主要介紹了如何使用Python和PyQt5來制作一個Memcached客戶端,以便我們可以輕松地與Memcached服務器進行交互,感興趣的小伙伴可以了解一下
    2023-06-06

最新評論