如何用Python实现Bellman Ford算法寻找最优数据包路由路径

需求说明 #

输入数据文件包含节点坐标，需计算节点间距离并匹配表格得到传输率。目标是找到至两个基站（BS1、BS2）中任意一个的最优路由路径，需满足以下优先级：

1. 传输率总和最大
2. 若传输率总和相同，链路总数最少

起始节点、链路及传输率存储于CSV/Excel文件中，使用Bellman-Ford算法实现该需求。

修正后的Python代码 #

import pandas as pd

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edges = []

    def add_edge(self, u, v, weight):
        # 存储边：起点、终点、传输率权重
        self.edges.append((u, v, weight))

class BellmanFord:
    def __init__(self, graph, source):
        self.graph = graph
        self.source = source
        # 初始化传输率总和：初始为负无穷（用于寻找最大值）
        self.max_trans_rate = {vertex: float('-inf') for vertex in graph.vertices}
        self.max_trans_rate[source] = 0
        # 记录前驱节点，用于回溯路径
        self.predecessors = {vertex: None for vertex in graph.vertices}
        # 记录路径的链路数
        self.path_length = {vertex: float('inf') for vertex in graph.vertices}
        self.path_length[source] = 0

    def run(self):
        vertex_count = len(self.graph.vertices)
        # 松弛操作：迭代顶点数-1次
        for _ in range(vertex_count - 1):
            updated = False
            for u, v, rate in self.graph.edges:
                # 如果经过u到v的传输率总和更大，则更新
                if self.max_trans_rate[u] != float('-inf') and self.max_trans_rate[u] + rate > self.max_trans_rate[v]:
                    self.max_trans_rate[v] = self.max_trans_rate[u] + rate
                    self.predecessors[v] = u
                    self.path_length[v] = self.path_length[u] + 1
                    updated = True
                # 传输率总和相同时，选择链路数更少的路径
                elif self.max_trans_rate[u] + rate == self.max_trans_rate[v]:
                    if self.path_length[u] + 1 < self.path_length[v]:
                        self.predecessors[v] = u
                        self.path_length[v] = self.path_length[u] + 1
                        updated = True
            if not updated:
                break  # 无更新时提前终止，优化性能

        # 检测正权环（存在正环则无法确定最优路径）
        for u, v, rate in self.graph.edges:
            if self.max_trans_rate[u] != float('-inf') and self.max_trans_rate[u] + rate > self.max_trans_rate[v]:
                print("检测到正权环，无法确定最优路径")
                return False
        return True

    def get_path(self, destination):
        # 回溯获取完整路径
        path = []
        current = destination
        while current is not None:
            path.append(current)
            current = self.predecessors[current]
            # 防止环导致的无限循环
            if len(path) > len(self.graph.vertices):
                print("路径中存在环")
                return []
        # 验证路径是否从起始节点出发
        if path[-1] != self.source:
            return []
        return path[::-1]

# 读取链路数据
df = pd.read_csv('Trans_rates_complete.csv')

# 收集所有节点：包含链路的起止节点及两个基站
all_nodes = set(df['start_car'].unique())
all_nodes.update(df['end_car'].unique())
all_nodes.add('BS1')
all_nodes.add('BS2')
vertices = list(all_nodes)

# 构建图并添加所有边
graph = Graph(vertices)
for _, row in df.iterrows():
    u = row['start_car']
    v = row['end_car']
    trans_rate = row['trans_rate']
    graph.add_edge(u, v, trans_rate)
    # 若链路为双向，取消下方注释添加反向边（根据实际场景调整）
    # graph.add_edge(v, u, trans_rate)

# 指定起始节点（替换为你的实际起始节点，例如'Car0'）
start_vertex = 'Car0'
bf = BellmanFord(graph, start_vertex)

# 运行算法并输出最优路径
if bf.run():
    # 获取到两个基站的路径信息
    path_bs1 = bf.get_path('BS1')
    rate_bs1 = bf.max_trans_rate['BS1']
    length_bs1 = bf.path_length['BS1']

    path_bs2 = bf.get_path('BS2')
    rate_bs2 = bf.max_trans_rate['BS2']
    length_bs2 = bf.path_length['BS2']

    # 按优先级选择最优路径
    print("=== 最优路径评估结果 ===")
    if rate_bs1 > rate_bs2:
        print(f"最优路径到BS1：{' -> '.join(path_bs1)}")
        print(f"总传输率：{rate_bs1:.2f}，链路数：{length_bs1}")
    elif rate_bs2 > rate_bs1:
        print(f"最优路径到BS2：{' -> '.join(path_bs2)}")
        print(f"总传输率：{rate_bs2:.2f}，链路数：{length_bs2}")
    else:
        # 传输率相同时选链路数更少的路径
        if length_bs1 <= length_bs2:
            print(f"最优路径到BS1：{' -> '.join(path_bs1)}")
            print(f"总传输率：{rate_bs1:.2f}，链路数：{length_bs1}")
        else:
            print(f"最优路径到BS2：{' -> '.join(path_bs2)}")
            print(f"总传输率：{rate_bs2:.2f}，链路数：{length_bs2}")

关键说明 #

1. 图结构适配：Graph类统一管理顶点和边信息，支持单向/双向链路配置（按需调整）。
2. Bellman-Ford算法改造：
   • 针对“最大化传输率”需求，将初始值设为负无穷，松弛条件改为判断传输率总和更大的场景。
   • 额外记录路径链路数，在传输率相同时选择更短路径。
   • 增加正权环检测，避免无限增大传输率的异常情况。
3. 路径选择逻辑：计算到两个基站的路径后，严格按照“传输率优先、链路数次之”的规则筛选最优路径。

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