# dijkstra算法實(shí)現(xiàn)，有向圖和路由的源點(diǎn)作為函數(shù)的輸入，最短路徑最為輸出
def dijkstra(graph,src):
 # 判斷圖是否為空，如果為空直接退出
 if graph is None:
 return None
 nodes = [i for i in range(len(graph))] # 獲取圖中所有節(jié)點(diǎn)
 visited=[] # 表示已經(jīng)路由到最短路徑的節(jié)點(diǎn)集合
 if src in nodes:
 visited.append(src)
 nodes.remove(src)
 else:
 return None
 distance={src:0} # 記錄源節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的距離
 for i in nodes:
 distance[i]=graph[src][i] # 初始化
 # print(distance)
 path={src:{src:[]}} # 記錄源節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的路徑
 k=pre=src
 while nodes:
 mid_distance=float('inf')
 for v in visited:
  for d in nodes:
  new_distance = graph[src][v]+graph[v][d]
  if new_distance < mid_distance:
   mid_distance=new_distance
   graph[src][d]=new_distance # 進(jìn)行距離更新
   k=d
   pre=v
 distance[k]=mid_distance # 最短路徑
 path[src][k]=[i for i in path[src][pre]]
 path[src][k].append(k)
 # 更新兩個(gè)節(jié)點(diǎn)集合
 visited.append(k)
 nodes.remove(k)
 print(visited,nodes) # 輸出節(jié)點(diǎn)的添加過(guò)程
 return distance,path
if __name__ == '__main__':
 graph_list = [ [0, 2, 1, 4, 5, 1],
  [1, 0, 4, 2, 3, 4],
  [2, 1, 0, 1, 2, 4],
  [3, 5, 2, 0, 3, 3],
  [2, 4, 3, 4, 0, 1],
  [3, 4, 7, 3, 1, 0]]

 distance,path= dijkstra(graph_list, 0) # 查找從源點(diǎn)0開(kāi)始帶其他節(jié)點(diǎn)的最短路徑
 print(distance,path)