# coding:utf-8

# Dijkstra算法——通过边实现松弛

# 指定一个点到其他各顶点的路径——单源最短路径

# 初始化图参数

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}}

# 每次找到离源点最近的一个顶点，然后以该顶点为重心进行扩展

# 最终的到源点到其余所有点的最短路径

# 一种贪婪算法

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

 """ 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离

  INF 为设定的无限远距离值

  此方法不能解决负权值边的图

 """

 book = set()

 minv = v0

 # 源顶点到其余各顶点的初始路程

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

 dis[v0] = 0

 while len(book)<len(G):

  book.add(minv)         # 确定当期顶点的距离

  for w in G[minv]:        # 以当前点的中心向外扩散

   if dis[minv] + G[minv][w] < dis[w]:   # 如果从当前点扩展到某一点的距离小与已知最短距离

    dis[w] = dis[minv] + G[minv][w]   # 对已知距离进行更新

  new = INF          # 从剩下的未确定点中选择最小距离点作为新的扩散点

  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("测试结果：")

print dis.values()

测试结果：

dict_values([0, 1, 8, 4, 13, 17])