Python案例如何用Networkx做Johnson算法

用Python与NetworkX实现Johnson算法：从理论到实战案例详解

📚 目录导读

• Johnson算法简介与核心原理

  

• NetworkX库概览及安装配置

• 基础单源最短路径求解

• 全源最短路径（Johnson算法）实战

• 带负权边的图处理与性能对比

• 常见问题与优化技巧（Q&A）

• 总结与应用场景

---

Johnson算法简介与核心原理

Johnson算法是解决全源最短路径问题（ASSP）的高效算法，尤其擅长处理稀疏图和含负权边的图，相比Floyd-Warshall算法（O(V³)），Johnson算法利用贝尔曼-福特+迪杰斯特拉的组合策略，将复杂度降至O(V² log V + V·E),在大型稀疏图中优势显著。

核心步骤：

• 加入虚拟源点，连接所有节点，边权为0
• 用贝尔曼-福特算法计算势函数（消除负权边）
• 用迪杰斯特拉算法计算每个节点的最短路径
• 还原真实路径长度

---

NetworkX库概览及安装配置

NetworkX 是Python中最流行的图论与网络分析库，支持有向/无向图、带权图、路径算法等,安装方式：

pip install networkx matplotlib

关键模块：

• nx.Graph() / nx.DiGraph()：创建图结构
• nx.add_weighted_edges_from()：批量添加带权边
• nx.johnson()：直接调用Johnson算法（核心函数）
• nx.single_source_dijkstra()：迪杰斯特拉单源路径

注：NetworkX已原生支持Johnson算法，无需手动实现贝尔曼-福特环节，但为深入理解原理,本文将展示手动实现与直接调用的对比。

---

案例一：基础单源最短路径求解

场景：已知城市交通网络（有向带权图）,求从节点A到所有其他节点的最短路径。

import networkx as nx
# 创建有向图
G = nx.DiGraph()
edges = [
    ('A', 'B', 2), 
    ('A', 'C', 5),
    ('B', 'C', 1),
    ('C', 'D', 3),
    ('B', 'D', 10)
]
G.add_weighted_edges_from(edges)
# 调用NetworkX的Dijkstra算法计算单源路径
path_lengths = nx.single_source_dijkstra_path_length(G, 'A')
paths = nx.single_source_dijkstra_path(G, 'A')
print("从A出发的最短距离：", dict(path_lengths))
print("从A出发的最短路径：", dict(paths))

输出：

从A出发的最短距离： {'A': 0, 'B': 2, 'C': 3, 'D': 6}
从A出发的最短路径： {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'B', 'C'], 'D': ['A', 'B', 'C', 'D']}

---

案例二：全源最短路径（Johnson算法）实战

场景：需要计算图中任意两节点之间的最短路径（例如物流配送中心的选址分析）。

1 直接调用NetworkX的johnson函数

import networkx as nx
import matplotlib.pyplot as plt
# 创建带负权的有向图（Johnson算法允许处理负权，但不能有负环）
G = nx.DiGraph()
edges = [
    (1, 2, 3),
    (1, 3, 8),
    (2, 4, -2),   # 负权边
    (3, 4, 5),
    (4, 5, 2),
    (2, 5, 10)
]
G.add_weighted_edges_from(edges)
# 计算全源最短路径
all_paths = nx.johnson(G, weight='weight')
print("全源最短路径结果：")
for source in all_paths:
    for target, path in all_paths[source].items():
        if source != target:
            print(f"{source} -> {target}: 路径 {path}, 距离 {sum(G[path[i]][path[i+1]]['weight'] for i in range(len(path)-1))}")

输出示例：

1 -> 2: 路径 [1, 2], 距离 3
1 -> 4: 路径 [1, 2, 4], 距离 1
2 -> 5: 路径 [2, 4, 5], 距离 0
...

2 手动实现Johnson算法（理解底层逻辑）

def johnson_manual(G):
    # 1. 添加虚拟节点s，连接所有节点，边权为0
    nodes = list(G.nodes())
    G_prime = G.copy()
    s = 's'
    G_prime.add_node(s)
    for v in nodes:
        G_prime.add_edge(s, v, weight=0)
    # 2. 贝尔曼-福特计算势函数h(v)
    try:
        h = nx.single_source_bellman_ford_path_length(G_prime, s)
    except nx.NetworkXUnbounded:
        raise ValueError("图中存在负权环")
    # 3. 重新调整边权: w'(u,v) = w(u,v) + h(u) - h(v)
    G_new = nx.DiGraph()
    for u, v, data in G.edges(data=True):
        new_weight = data['weight'] + h[u] - h[v]
        G_new.add_edge(u, v, weight=new_weight)
    # 4. 对每个节点运行Dijkstra
    all_paths = {}
    for source in nodes:
        distances, paths = nx.single_source_dijkstra(G_new, source)
        all_paths[source] = paths
    return all_paths
# 使用相同图数据测试
manual_paths = johnson_manual(G)
print("手动实现Johnson算法结果：", manual_paths)

---

案例三：带负权边的图处理与性能对比

场景：电商价格网络（节点为商品，边为优惠后价格差），存在负边（降价促销）,需检测负环并计算全源路径。

1 负环检测演示

# 构造一个包含负环的图（错误示例）
G_neg_cycle = nx.DiGraph()
G_neg_cycle.add_weighted_edges_from([
    (1, 2, 1),
    (2, 3, -3),
    (3, 1, 2)   # 形成环1-2-3-1，总权值为0？实际为0？计算：1-2:1, 2-3:-3, 3-1:2 => 总=0，无负环
])
# 但若改为(3,1,-1)则形成1+(-3)+(-1)=-3负环
G_neg_cycle.add_edge(3, 1, weight=-1)  # 修改后
try:
    nx.johnson(G_neg_cycle)
except nx.NetworkXUnbounded:
    print("检测到负权环，Johnson算法无法处理！")

2 性能对比：Johnson vs Floyd-Warshall

import time
import random
# 生成随机稀疏图（100节点，500边）
def generate_random_graph(nodes, edges):
    G = nx.DiGraph()
    G.add_nodes_from(range(nodes))
    for _ in range(edges):
        u = random.randint(0, nodes-1)
        v = random.randint(0, nodes-1)
        if u != v:
            w = random.randint(-5, 10)
            if w >= 0:  # 避免负环复杂化
                G.add_edge(u, v, weight=w)
    return G
G_large = generate_random_graph(100, 500)
# 测试Johnson算法时间
start = time.time()
nx.johnson(G_large, weight='weight')
johnson_time = time.time() - start
# 测试Floyd-Warshall算法时间（手动实现简单版）
start = time.time()
dist = dict(nx.floyd_warshall_numpy(G_large, weight='weight'))
floyd_time = time.time() - start
print(f"Johnson算法耗时: {johnson_time:.4f}秒")
print(f"Floyd-Warshall耗时: {floyd_time:.4f}秒")

在稀疏图中，Johnson算法通常比Floyd-Warshall快5-20倍。

---

常见问题与优化技巧（Q&A）

Q1: Johnson算法适用于带负环的图吗？

A: 不适用，算法中的贝尔曼-福特阶段会检测负环，若检测到则抛出异常,必须确保图无负环。

Q2: NetworkX的johnson()函数是否自动处理负权边？

A: 是的，该函数内部已实现势函数调整，直接传入权重参数即可,无需预处理。

Q3: 当节点数超过1000时，建议使用哪个算法？

A: 对于稀疏图（E << V²），优先选择Johnson算法；对于稠密图（E ≈ V²），Floyd-Warshall更合适，也可以使用nx.all_pairs_dijkstra_path()（无负权时更快）。

Q4: 如何可视化路径结果？

A: 使用matplotlib与networkx绘图，

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue')
# 高亮某条路径
path_edges = list(zip(all_paths[1][5][:-1], all_paths[1][5][1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2)
plt.show()

---

总结与应用场景

应用领域	具体案例	算法优势
交通网络规划	物流中心选址、航班航线优化	处理大型稀疏图
社交网络分析	最短关系链、影响力传播路径	支持负边（如反向关注）
电商定价系统	优惠组合最低价计算、供应链成本优化	检测负环避免无限套利
游戏AI路径寻路	地图节点间最短导航	比A*更稳健（无启发函数限制）

核心技术点回顾：

• 使用nx.johnson(G)即可一键全源最短路径
• 负权边自动处理，但必须保证无负环
• 性能选择：稀疏图→Johnson，稠密图→Floyd-Warshall

通过以上案例，您已掌握如何用NetworkX实现Johnson算法进行图分析，建议在真实项目中优先使用库函数，但在算法竞赛或定制场景中,手动实现可提供更大的灵活性。