本文借鑒于張廣河教授主編的《數(shù)據(jù)結(jié)構(gòu)》，對(duì)其中的代碼進(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}。
• 選擇一條長(zhǎng)度最小的最短路徑，該路徑的終點(diǎn)w屬于V-S，將w并入S，并將該最短路徑的長(zhǎng)度記為Dw。
• 對(duì)于V-S中任一頂點(diǎn)是s，將源點(diǎn)到頂點(diǎn)s的最短路徑長(zhǎng)度記為Ds，并將頂點(diǎn)w到頂點(diǎn)s的弧的權(quán)值記為Dws，若Dw+Dws
• 則將源點(diǎn)到頂點(diǎn)s的最短路徑長(zhǎng)度修改為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)的最短路徑長(zhǎng)度。
• 使用列表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)的最短路徑的長(zhǎng)度
  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
            
            
          

輸出結(jié)果如下：

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

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