（1）Bellman Ford Algorithm，贝尔曼-福特算法，图中搜索遍历最短路径的一种适应性强的算法。Bellman Ford Algorithm可以应用在负值边权的图，这和dijkstra最短路径算法有差异，dijkstra不适应于存在负边权的图。Bellman Ford Algorithm是一种广度优先搜索最短路径策略。经过全部迭代后，每一个节点中保存的权值（node weight），即为从起始点（一般为0）到该节点的最小路径值。
（2）Bellman Ford Algorithm在迭代开始时候，选一个顶点V，然后在队列Q中保存与顶点V相邻接的节点，并更新相邻接的节点权值。但是，要特别注意，所谓在队列Q中保存与顶点相邻接的节点，只发生在相邻接的节点权值更新时候才保存，否则该邻接节点不加入队列Q。
比如，顶点V节点权值为5，从V（from_node）出发，与V相邻接的节点有V1,V2(这两个为 to_node)。假设V1当前权值为8，V与V1邻接的边权(edge_weight)为1，5+1=6 < 8，于是更新V1的节点权值（node_weight）为最新的6，并同时把节点V1加入队列Q。假设V2当前节点权值为6，V与V2邻接的边权(edge_weight)为4，5+4=9 > 6，所以V2节点权值不予更新，仍为6，且V2节点不能加入队列。
（3）每迭代一轮，删掉队列最左边（头部）的节点。
import random
import networkx as nx
import matplotlib.pyplot as plt
WEIGHT = 'weight'
def my_graph():
G = nx.gnm_random_graph(n=8, m=10)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos,
node_color='green',
node_size=300,
font_size=10,
font_color='white',
edge_color='gray',
width=1,
with_labels=True)
# 每条边增加随机权值
for e in G.edges(data=True):
e[2][WEIGHT] = random.randint(1, 9)
my_edge_labels = nx.get_edge_attributes(G, WEIGHT)
nx.draw_networkx_edge_labels(G, pos, edge_labels=my_edge_labels)
for n in G.nodes():
G.nodes[n][WEIGHT] = float('inf')
V = 0
G.nodes[V][WEIGHT] = 0
print('G.edges(data=True)', G.edges(data=True))
print('G.nodes(data=True)', G.nodes(data=True))
bellman_ford_algorithm(G, V)
plt.show()
# 基于队列，广度搜索遍历,贝尔曼-福特算法
def bellman_ford_algorithm(G, V):
Q = [V]
while True:
if len(Q) == 0:
break
print('-----')
print('Q-', Q)
visit_node = Q[0]
print('访问', visit_node)
neighbors = nx.neighbors(G, visit_node)
for to_node in neighbors:
update_weight(G, visit_node, to_node, Q)
del (Q[0])
print('Q--', Q)
print('nodes', G.nodes(data=True))
path = find_short_path(G, 5)
print('path', path)
# 寻找从0节点到v的最短路径
def find_short_path(G, v):
path = [v]
loop_flag = True
while loop_flag:
v_node_weight = G.nodes[v][WEIGHT]
ok_node = None
for from_node in nx.neighbors(G, v):
from_node_weight = G.nodes[from_node][WEIGHT]
edge_weight = G.get_edge_data(u=from_node, v=v)[WEIGHT]
if (from_node_weight + edge_weight) == v_node_weight:
ok_node = from_node
break
if ok_node != None:
path.append(ok_node)
if ok_node == 0:
loop_flag = False
else:
v = ok_node
list.reverse(path)
return path
def update_weight(G, from_node, to_node, Q):
form_node_weight = G.nodes[from_node][WEIGHT]
edge_weight = G.get_edge_data(u=from_node, v=to_node)[WEIGHT]
to_node_weight = G.nodes[to_node][WEIGHT]
sum_weight = form_node_weight + edge_weight
if (sum_weight) < to_node_weight:
G.nodes[to_node][WEIGHT] = sum_weight
Q.append(to_node)
if __name__ == '__main__':
my_graph()
生成图：
运行日志：
G.edges(data=True) [(0, 4, {'weight': 7}), (0, 2, {'weight': 3}), (0, 6, {'weight': 2}), (1, 2, {'weight': 5}), (2, 3, {'weight': 6}), (2, 4, {'weight': 8}), (3, 5, {'weight': 2}), (4, 5, {'weight': 8}), (4, 6, {'weight': 5}), (6, 7, {'weight': 8})]
G.nodes(data=True) [(0, {'weight': 0}), (1, {'weight': inf}), (2, {'weight': inf}), (3, {'weight': inf}), (4, {'weight': inf}), (5, {'weight': inf}), (6, {'weight': inf}), (7, {'weight': inf})]
-----
Q- [0]
访问 0
Q-- [4, 2, 6]
-----
Q- [4, 2, 6]
访问 4
Q-- [2, 6, 5]
-----
Q- [2, 6, 5]
访问 2
Q-- [6, 5, 3, 1]
-----
Q- [6, 5, 3, 1]
访问 6
Q-- [5, 3, 1, 7]
-----
Q- [5, 3, 1, 7]
访问 5
Q-- [3, 1, 7]
-----
Q- [3, 1, 7]
访问 3
Q-- [1, 7, 5]
-----
Q- [1, 7, 5]
访问 1
Q-- [7, 5]
-----
Q- [7, 5]
访问 7
Q-- [5]
-----
Q- [5]
访问 5
Q-- []
nodes [(0, {'weight': 0}), (1, {'weight': 8}), (2, {'weight': 3}), (3, {'weight': 9}), (4, {'weight': 7}), (5, {'weight': 11}), (6, {'weight': 2}), (7, {'weight': 10})]
path [0, 2, 3, 5]