本文目录导读：
我来帮你了解如何使用NetworkX实现Bellman-Ford算法，NetworkX内置了Bellman-Ford算法,下面是几个实用的案例：
基础用法示例
import networkx as nx
import matplotlib.pyplot as plt
# 创建一个有向图
G = nx.DiGraph()
# 添加边（带权重）
edges = [
('A', 'B', 4),
('A', 'C', 2),
('B', 'C', -3), # 注意：这里使用了负权重
('B', 'D', 2),
('C', 'D', 3),
('E', 'A', 1)
]
G.add_weighted_edges_from(edges)
# 执行Bellman-Ford算法，计算从节点'A'到所有节点的最短路径
try:
# 方法1：使用bellman_ford_path
distances = nx.single_source_bellman_ford_path_length(G, 'A')
paths = nx.single_source_bellman_ford_path(G, 'A')
print("从节点A到各节点的最短距离:")
for node, dist in distances.items():
print(f"A -> {node}: 距离 = {dist}, 路径 = {paths[node]}")
except nx.NetworkXUnbounded:
print("图中存在负权环!")
检测负权环
import networkx as nx
def detect_negative_cycle(G, source='A'):
"""
检测图中是否存在负权环
"""
try:
# 尝试计算最短路径
distances = nx.single_source_bellman_ford_path_length(G, source)
print("没有检测到负权环")
return False
except nx.NetworkXUnbounded as e:
print(f"检测到负权环: {e}")
return True
# 创建包含负权环的图
G_with_cycle = nx.DiGraph()
edges_with_cycle = [
('A', 'B', 1),
('B', 'C', -2),
('C', 'A', -1), # 形成一个负权环
('B', 'D', 3)
]
G_with_cycle.add_weighted_edges_from(edges_with_cycle)
# 检测负权环
detect_negative_cycle(G_with_cycle)
完整应用案例 - 交通网络分析
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
class TrafficNetworkAnalyzer:
def __init__(self):
self.graph = nx.DiGraph()
def create_traffic_network(self):
"""创建模拟交通网络"""
# 城市节点
cities = ['北京', '天津', '上海', '南京', '杭州', '广州']
# 添加道路（带通行时间，可以负值表示节省时间）
roads = [
('北京', '天津', 30), # 30分钟
('天津', '北京', 25),
('北京', '上海', 120), # 2小时
('上海', '南京', 60),
('南京', '杭州', 45),
('上海', '杭州', 90),
('广州', '上海', 180),
('天津', '南京', 90),
('北京', '广州', -10), # 特殊情况：夜班车实际节省时间
]
self.graph.add_weighted_edges_from(roads)
return self.graph
def find_shortest_paths(self, start_city):
"""查找从起始城市到所有城市的最短路径"""
try:
# 计算最短路径距离
distances = nx.single_source_bellman_ford_path_length(
self.graph, start_city
)
# 计算具体路径
paths = nx.single_source_bellman_ford_path(
self.graph, start_city
)
print(f"\n从{start_city}出发的最短路径规划:")
print("-" * 50)
for city in self.graph.nodes:
if city != start_city and city in distances:
print(f"到达{city}: 时间={distances[city]}分钟")
print(f"路径: {' -> '.join(paths[city])}")
print()
return distances, paths
except nx.NetworkXUnbounded:
print("检测到负时间环！请检查交通数据")
return None, None
def find_all_pairs_shortest_paths(self):
"""查找所有城市对之间的最短路径"""
print("所有城市对的最短路径（Bellman-Ford）:")
print("=" * 60)
for start in self.graph.nodes:
try:
paths = nx.single_source_bellman_ford_path(
self.graph, start
)
for end in self.graph.nodes:
if start != end and end in paths:
path_str = ' -> '.join(paths[end])
length = nx.path_weight(self.graph, paths[end], 'weight')
print(f"{start} -> {end}: {path_str} (时间={length}分钟)")
except nx.NetworkXUnbounded:
print(f"从{start}出发存在负权环")
def visualize_network(self):
"""可视化交通网络"""
plt.figure(figsize=(12, 8))
# 布局
pos = nx.spring_layout(self.graph, seed=42)
# 绘制节点
nx.draw_networkx_nodes(self.graph, pos,
node_color='lightblue',
node_size=700)
# 绘制边
nx.draw_networkx_edges(self.graph, pos,
edge_color='gray',
arrows=True,
arrowsize=20)
# 添加标签
nx.draw_networkx_labels(self.graph, pos, font_size=10)
# 添加边权重
edge_labels = nx.get_edge_attributes(self.graph, 'weight')
nx.draw_networkx_edge_labels(self.graph, pos,
edge_labels=edge_labels)
plt.title("交通网络图（边权表示通行时间/分钟）")
plt.axis('off')
plt.tight_layout()
plt.show()
# 使用示例
if __name__ == "__main__":
# 创建交通网络分析器
analyzer = TrafficNetworkAnalyzer()
# 创建网络
graph = analyzer.create_traffic_network()
# 查找从北京出发的最短路径
distances, paths = analyzer.find_shortest_paths('北京')
# 查找所有城市对之间的最短路径
analyzer.find_all_pairs_shortest_paths()
# 可视化
analyzer.visualize_network()
自定义Bellman-Ford实现
import networkx as nx
def custom_bellman_ford(G, source):
"""
自定义Bellman-Ford算法实现
"""
# 初始化距离和路径
distance = {node: float('inf') for node in G.nodes}
predecessor = {node: None for node in G.nodes}
distance[source] = 0
# 获取所有边
edges = list(G.edges(data='weight', default=1))
# 进行V-1次松弛
for _ in range(len(G.nodes) - 1):
for u, v, weight in edges:
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
predecessor[v] = u
# 检测负权环
for u, v, weight in edges:
if distance[u] + weight < distance[v]:
raise nx.NetworkXUnbounded("图中存在负权环")
# 重构路径
paths = {}
for node in G.nodes:
if node == source:
paths[node] = [source]
elif predecessor[node] is not None:
path = []
current = node
while current is not None:
path.insert(0, current)
current = predecessor[current]
paths[node] = path
else:
paths[node] = []
return distance, paths
# 测试自定义实现
G = nx.DiGraph()
G.add_weighted_edges_from([
('A', 'B', 4),
('A', 'C', 2),
('B', 'C', 3),
('B', 'D', 2),
('C', 'D', 1)
])
dist, paths = custom_bellman_ford(G, 'A')
print("自定义Bellman-Ford结果:")
for node in G.nodes:
print(f"A -> {node}: 距离={dist[node]}, 路径={paths[node]}")
-
NetworkX API:
single_source_bellman_ford_path_length(): 计算最短距离single_source_bellman_ford_path(): 计算具体路径- 异常
NetworkXUnbounded表示存在负权环
-
应用场景:
- 负权边：如时间节省、成本折扣等
- 检测负权环：如套利机会检测
- 交通网络：考虑拥堵折扣
-
注意事项:
- Bellman-Ford适用于有向图
- 可以处理负权边
- 时间复杂度O(VE)，比Dijkstra慢但更通用
- 需要处理负权环异常
这些示例展示了Bellman-Ford算法在不同场景下的应用,特别适合处理包含负权边的图。
