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

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

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
            
            
          

輸出結果如下：

請輸入源點
a
請輸入終點
f
從頂點a到頂點f的最短路徑為：
['a', 'c', 'e', 'f']
最短路徑長度為：17

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