本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法)。分享給大家供大家參考，具體如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# 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 disdis = Dijkstra(G,v0=1)print("服務(wù)器之家測(cè)試結(jié)果：")print dis.values() |
運(yùn)行結(jié)果：
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
原文鏈接：https://www.cnblogs.com/hanahimi/p/4692638.html
