python数据结构与算法——图的最短路径（Bellman-Ford算法）解决负权边，, 1 # Bellm

python数据结构与算法——图的最短路径（Bellman-Ford算法）解决负权边，, 1 # Bellm

 1 # Bellman-Ford核心算法 2 # 对于一个包含n个顶点，m条边的图, 计算源点到任意点的最短距离 3 # 循环n-1轮，每轮对m条边进行一次松弛操作 4  5 # 定理： 6 # 在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边 7 # 最短路径肯定是一个不包含回路的简单路径（回路包括正权回路与负权回路） 8 # 1. 如果最短路径中包含正权回路，则去掉这个回路，一定可以得到更短的路径 9 # 2. 如果最短路径中包含负权回路，则每多走一次这个回路，路径更短，则不存在最短路径10 # 因此最短路径肯定是一个不包含回路的简单路径，即最多包含n-1条边，所以进行n-1次松弛即可11 12 13 G = {1:{1:0, 2:-3, 5:5},14      2:{2:0, 3:2},15      3:{3:0, 4:3},16      4:{4:0, 5:2},17      5:{5:0}}18 19 20 21 def getEdges(G):22     """ 输入图G，返回其边与端点的列表 """23     v1 = []     # 出发点         24     v2 = []     # 对应的相邻到达点25     w  = []     # 顶点v1到顶点v2的边的权值26     for i in G:27         for j in G[i]:28             if G[i][j] != 0:29                 w.append(G[i][j])30                 v1.append(i)31                 v2.append(j)32     return v1,v2,w33 34 class CycleError(Exception):35     pass36 37 def Bellman_Ford(G, v0, INF=999):38     v1,v2,w = getEdges(G)39     40     # 初始化源点与所有点之间的最短距离41     dis = dict((k,INF) for k in G.keys())42     dis[v0] = 043 44     # 核心算法45     for k in range(len(G)-1):   # 循环 n-1轮46         check = 0           # 用于标记本轮松弛中dis是否发生更新47         for i in range(len(w)):     # 对每条边进行一次松弛操作48             if dis[v1[i]] + w[i] < dis[v2[i]]:49                 dis[v2[i]] = dis[v1[i]] + w[i]50                 check = 151         if check == 0: break52     53     # 检测负权回路54     # 如果在 n-1 次松弛之后，最短路径依然发生变化，则该图必然存在负权回路55     flag = 056     for i in range(len(w)):             # 对每条边再尝试进行一次松弛操作57         if dis[v1[i]] + w[i] < dis[v2[i]]: 58             flag = 159             break60     if flag == 1:61 #         raise CycleError()62         return False63     return dis64 65 v0 = 166 dis = Bellman_Ford(G, v0)67 print dis.values()

python数据结构与算法——图的最短路径（Bellman-Ford算法）解决负权边