国产一级一级国产,久久男人免费视频,欧美成人性生活

本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法)。分享給大家供大家參考，具體如下：

				?

									# coding:utf-8

									# Dijkstra算法——通過(guò)邊實(shí)現(xiàn)松弛

									# 指定一個(gè)點(diǎn)到其他各頂點(diǎn)的路徑——單源最短路徑

									# 初始化圖參數(shù)

									G = {1:{1:0, 2:1, 3:12},

									  2:{2:0, 3:9, 4:3},

									  3:{3:0, 5:5},

									  4:{3:4, 4:0, 5:13, 6:15},

									  5:{5:0, 6:4},

									  6:{6:0}}

									# 每次找到離源點(diǎn)最近的一個(gè)頂點(diǎn)，然后以該頂點(diǎn)為重心進(jìn)行擴(kuò)展

									# 最終的到源點(diǎn)到其余所有點(diǎn)的最短路徑

									# 一種貪婪算法

									def Dijkstra(G,v0,INF=999):

									 """ 使用 Dijkstra 算法計(jì)算指定點(diǎn) v0 到圖 G 中任意點(diǎn)的最短路徑的距離

									  INF 為設(shè)定的無(wú)限遠(yuǎn)距離值

									  此方法不能解決負(fù)權(quán)值邊的圖

									 """

									 book = set()

									 minv = v0

									 # 源頂點(diǎn)到其余各頂點(diǎn)的初始路程

									 dis = dict((k,INF) for k in G.keys())

									 dis[v0] = 0

									 while len(book)<len(G):

									  book.add(minv)         # 確定當(dāng)期頂點(diǎn)的距離

									  for w in G[minv]:        # 以當(dāng)前點(diǎn)的中心向外擴(kuò)散

									   if dis[minv] + G[minv][w] < dis[w]:   # 如果從當(dāng)前點(diǎn)擴(kuò)展到某一點(diǎn)的距離小與已知最短距離

									    dis[w] = dis[minv] + G[minv][w]   # 對(duì)已知距離進(jìn)行更新

									  new = INF          # 從剩下的未確定點(diǎn)中選擇最小距離點(diǎn)作為新的擴(kuò)散點(diǎn)

									  for v in dis.keys():

									   if v in book: continue

									   if dis[v] < new:

									    new = dis[v]

									    minv = v

									 return dis

									dis = Dijkstra(G,v0=1)

									print("服務(wù)器之家測(cè)試結(jié)果：")

									print dis.values()