亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

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

系統(tǒng) 1906 0

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

從某源點(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。
  • 對于V-S中任一頂點(diǎn)是s,將源點(diǎn)到頂點(diǎn)s的最短路徑長度記為Ds,并將頂點(diǎn)w到頂點(diǎn)s的弧的權(quán)值記為Dws,若Dw+Dws
  • 則將源點(diǎn)到頂點(diǎn)s的最短路徑長度修改為Dw+Ds=ws。
  • 重復(fù)執(zhí)行2和3,知道S=V。
  • 為了實(shí)現(xiàn)算法,
  • 使用鄰接矩陣Arcs存儲有向網(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存儲源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長度。
  • 使用列表Path存儲每一條最短路徑中倒數(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)] #存儲源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑的長度
  Path=[[] for i in range(self.VertexNum)] #存儲每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)
  flag=[[] for i in range(self.VertexNum)] #記錄每一個(gè)頂點(diǎn)是否求得最短路徑
  index=0
  #初始化
  while index
            
            
          

輸出結(jié)果如下:

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

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲视频免费在线观看 | 欧美 日产 国产精品 | 四虎视频网站 | 乱子伦有声小说mp3 仑乱高清在线一级播放 | 午夜性色福利视频在线视频 | 亚洲欧美综合一区 | 婷婷国产成人久久精品激情 | 尤物精品视频在线观看 | 看全色黄大色大片免费视频 | 一级播放 | 国产免费私人影院永久免费 | 污宅男666在线永久免费观看 | 97国内免费久久久久久久久久 | 伊人网址| 好吊色青青青国产欧美日韩 | 日日摸夜夜嗷嗷叫日日拍 | 欧美另类黑人巨大videos | 亚洲美女亚洲精品久久久久 | 99久热国产精品视频尤物不卡 | 91最新91精品91蝌蚪 | 日本免费一级视频 | 亚洲精品中文字幕久久久久久 | 亚洲欧美日韩一区二区在线观看 | 欧美一级黄色录像 | 日本一区二区三区高清在线观看 | 欧美中文字幕 | 奇米网狠狠 | 青草伊伊 | 亚洲精品乱码久久久久蜜桃 | 日日摸夜夜摸无需播放器 | 久久精品免视看国产成人2021 | 91在线视频免费播放 | 成人综合网址 | 一区二区三区 日韩 | 免费的毛片 | 久久99热这里只有精品国产 | 日本高清不卡一区久久精品 | 亚洲欧美激情综合第一区 | 日本特黄a级高清免费大片18 | 亚洲高清中文字幕综合网 | 久久久久在线 |