def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路徑，并返回該路徑和代價
  print("Start Dijstra Path……")
  path=[]#s-d的最短路徑
  n=len(network)#鄰接矩陣維度，即節(jié)點(diǎn)個數(shù)
  fmax=999
  w=[[0 for i in range(n)]for j in range(n)]#鄰接矩陣轉(zhuǎn)化成維度矩陣，即0→max
  book=[0 for i in range(n)]#是否已經(jīng)是最小的標(biāo)記列表
  dis=[fmax for i in range(n)]#s到其他節(jié)點(diǎn)的最小距離
  book[s-1]=1#節(jié)點(diǎn)編號從1開始，列表序號從0開始
  midpath=[-1 for i in range(n)]#上一跳列表
  for i in range(n):
    for j in range(n):
      if network[i][j]!=0:
        w[i][j]=network[i][j]#0→max
      else:
        w[i][j]=fmax
      if i==s-1 and network[i][j]!=0:#直連的節(jié)點(diǎn)最小距離就是network[i][j]
        dis[j]=network[i][j]
  for i in range(n-1):#n-1次遍歷，除了s節(jié)點(diǎn)
    min=fmax
    for j in range(n):
      if book[j]==0 and dis[j]<min:#如果未遍歷且距離最小
        min=dis[j]
        u=j
    book[u]=1
    for v in range(n):#u直連的節(jié)點(diǎn)遍歷一遍
      if dis[v]>dis[u]+w[u][v]:
        dis[v]=dis[u]+w[u][v]
        midpath[v]=u+1#上一跳更新
  j=d-1#j是序號
  path.append(d)#因?yàn)榇鎯Φ氖巧弦惶?，所以先加入目的?jié)點(diǎn)d，最后倒置
  while(midpath[j]!=-1):
    path.append(midpath[j])
    j=midpath[j]-1
  path.append(s)
  path.reverse()#倒置列表
  print(path)
  #print(midpath)
  print(dis)
  #return path

network=[[0,1,0,2,0,0],
     [1,0,2,4,3,0],
     [0,2,0,0,1,4],
     [2,4,0,0,6,0],
     [0,3,1,6,0,2],
     [0,0,4,0,2,0]]
Dijkstra(network,1,6)