Bellman-Ford算法各场景运行时间Python测算、用例构造及可视化

1. 运行时间统计逻辑 #

统计运行时间采用Python标准库time中的perf_counter()方法，该方法计时精度可达微秒级，适合短周期代码运行时长测算。
统计时遵循两个原则：

• 将算法核心计算逻辑与IO输出逻辑拆分，避免打印操作占用的时间干扰性能统计结果
• 对同规模同一场景的测试重复运行多次，取平均耗时作为最终结果，消除系统调度带来的偶然误差

原有代码改造点：

• 保留原算法核心松弛、负环检测逻辑，新增打印控制参数，默认关闭结果输出，将距离计算结果、负环检测结果作为返回值返回
• 计时逻辑放在算法调用外层，不侵入核心计算流程

2. 三类测试场景的图结构构造 #

三类场景的核心差异体现在松弛过程中距离更新操作的频次，对应构造逻辑如下：

• 最优场景：构造以源点为中心的星型有向图，所有边均从源点直接指向其余节点，权值为正整数。第一轮松弛即可完成所有节点的最短距离计算，后续V-2轮遍历所有边时无任何距离更新操作，赋值操作最少，耗时最低。
• 平均场景：构造随机连通有向图，先添加链式边保证图连通，再随机添加若干条跨节点边，所有边权值为正整数。松弛过程中仅前几轮存在部分距离更新操作，后续轮次无更新，更新操作数量介于最优和最坏场景之间。
• 最坏场景：构造节点按顺序连接的链式有向图，边为0→1、1→2、…、V-2→V-1，权值均为1，源点为0。该结构下第k轮松弛仅能更新第k个节点的最短距离，必须跑满V-1轮才能得到所有节点的正确距离，每轮都存在距离更新操作，赋值操作最多，耗时最高。

3. 性能差异可视化 #

采用matplotlib库绘制折线图实现直观对比：

• X轴为测试用图的节点规模，设置梯度递增的节点数序列（如10到200，步长20）
• Y轴为对应规模下场景的平均运行耗时，单位为秒
• 用不同颜色、标记的折线分别代表最优、平均、最坏三类场景，添加图例、坐标轴标签、网格线辅助阅读，可清晰观察到最坏场景耗时随节点规模增长的斜率远高于其余两类场景。

完整调整后代码 #

import time
import random
import matplotlib.pyplot as plt

# 图结构类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数量
        self.graph = []

    # 添加边
    def addEdge(self, u, v, w):
        self.graph.append([u, v, w])
        
    # 打印结果工具方法
    def printArr(self, dist):
        print("顶点到源点的最短距离")
        for i in range(self.V):
            print("{0}\t\t{1}".format(i, dist[i]))
    
    # Bellman-Ford核心算法
    def BellmanFord(self, src, print_res=False):
        # 初始化距离数组
        dist = [float("Inf")] * self.V
        dist[src] = 0

        # 松弛V-1轮
        for _ in range(self.V - 1):
            updated = False
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        updated = True
            # 可选提前终止优化：某轮无更新直接跳出，取消注释即可启用
            # if not updated:
            #     break

        # 检测负权环
        has_neg_cycle = False
        for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                        has_neg_cycle = True
                        break
        
        if print_res:
            if has_neg_cycle:
                print("图中存在负权环")
            else:
                self.printArr(dist)
        return dist, has_neg_cycle

# 构造最优场景：源点直连所有节点的星型图
def generate_best_case(v_num):
    g = Graph(v_num)
    for i in range(1, v_num):
        g.addEdge(0, i, random.randint(1, 10))
    return g

# 构造最坏场景：顺序连接的链式图
def generate_worst_case(v_num):
    g = Graph(v_num)
    for i in range(v_num - 1):
        g.addEdge(i, i+1, 1)
    return g

# 构造平均场景：随机连通图
def generate_average_case(v_num):
    g = Graph(v_num)
    # 基础链式边保证连通
    for i in range(v_num - 1):
        g.addEdge(i, i+1, random.randint(1, 10))
    # 随机添加额外边
    for _ in range(v_num):
        u = random.randint(0, v_num-1)
        v = random.randint(0, v_num-1)
        if u != v:
            g.addEdge(u, v, random.randint(1, 10))
    return g

# 性能测试配置
test_sizes = [10, 20, 30, 50, 80, 120, 160, 200]  # 测试节点规模梯度
repeat_times = 5  # 每组测试重复次数，取平均消除误差
best_times = []
avg_times = []
worst_times = []

for size in test_sizes:
    # 最优场景耗时统计
    total_t = 0
    for _ in range(repeat_times):
        g = generate_best_case(size)
        start = time.perf_counter()
        g.BellmanFord(0)
        end = time.perf_counter()
        total_t += end - start
    best_times.append(total_t / repeat_times)

    # 平均场景耗时统计
    total_t = 0
    for _ in range(repeat_times):
        g = generate_average_case(size)
        start = time.perf_counter()
        g.BellmanFord(0)
        end = time.perf_counter()
        total_t += end - start
    avg_times.append(total_t / repeat_times)

    # 最坏场景耗时统计
    total_t = 0
    for _ in range(repeat_times):
        g = generate_worst_case(size)
        start = time.perf_counter()
        g.BellmanFord(0)
        end = time.perf_counter()
        total_t += end - start
    worst_times.append(total_t / repeat_times)

# 绘制性能对比图
plt.figure(figsize=(10, 6))
plt.plot(test_sizes, best_times, label='最优场景', marker='o', color='#2ecc71')
plt.plot(test_sizes, avg_times, label='平均场景', marker='s', color='#3498db')
plt.plot(test_sizes, worst_times, label='最坏场景', marker='^', color='#e74c3c')
plt.xlabel('节点数量')
plt.ylabel('平均运行耗时（秒）')
plt.title('Bellman-Ford算法不同场景性能对比')
plt.legend()
plt.grid(alpha=0.3)
plt.show()

# 原示例代码（需要测试可取消注释）
# g = Graph(5)
# g.addEdge(0, 1, -1)
# g.addEdge(0, 2, 4)
# g.addEdge(1, 2, 3)
# g.addEdge(1, 3, 2)
# g.addEdge(1, 4, 2)
# g.addEdge(3, 2, 5)
# g.addEdge(3, 1, 1)
# g.addEdge(4, 3, -3)
# g.BellmanFord(0, print_res=True)

内容的提问来源于stack exchange，提问作者sarah