Python案例如何用Networkx做Bellman-Ford

wen python案例 2026-07-15 195

本文目录导读：

基础用法示例
检测负权环
完整应用案例 - 交通网络分析
自定义Bellman-Ford实现

我来帮你了解如何使用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算法在不同场景下的应用,特别适合处理包含负权边的图。

本文地址： https://www.bmjup.com/post/21957.html