Python Dijkstra 算法实现网络主备份路径规划

import numpy as np
import pandas as pd
import heapq

def dijkstra(start, end, weights):
    queue = [(0, start, [])]
    seen = set()
    min_distance = {start: 0}
    while queue:
        (distance, v, path) = heapq.heappop(queue)
        if v not in seen:
            seen.add(v)
            path = path + [v]
            if v == end:
                return np.array(path) + 1
            for next_node in range(weights.shape[0]):
                if weights[v][next_node] > 0 and next_node not in seen:
                    old_distance = min_distance.get(next_node, None)
                    new_distance = min_distance[v] + weights[v][next_node]
                    if old_distance is None or new_distance < old_distance:
                        heapq.heappush(queue, (new_distance, next_node, path))
                        min_distance[next_node] = new_distance
    return []

def check_validity(main_path, backup_path, logical_network, physical_network, existing_paths):
    if physical_network[main_path[:-1]-1, main_path[1:]-1].min() < logical_network[main_path[0]-1, main_path[-1]-1]:
        return False
    if physical_network[backup_path[:-1]-1, backup_path[1:]-1].min() < logical_network[backup_path[0]-1, backup_path[-1]-1]:
        return False
    if tuple(backup_path) in existing_paths:
        return False
    return True

def get_main_backup_paths(logical_network, physical_network):
    existing_paths = set()
    paths = {}
    for i in range(logical_network.shape[0]):
        for j in range(i+1, logical_network.shape[1]):
            if logical_network[i, j] > 0:
                main_path = dijkstra(i, j, physical_network)
                backup_path = dijkstra(i, j, physical_network)
                if not check_validity(main_path, backup_path, logical_network, physical_network, existing_paths):
                    print(f'Cannot find valid paths for link ({i+1}, {j+1}).')
                    continue
                paths[(i+1, j+1)] = (main_path, backup_path)
                physical_network[backup_path[:-1]-1, backup_path[1:]-1] = 0
                existing_paths.add(tuple(backup_path))
    return paths

physical_network = pd.read_excel('物理网络1.xls', header=None).to_numpy()
logical_network = pd.read_excel('逻辑网络1.xls', header=None).to_numpy()
paths = get_main_backup_paths(logical_network, physical_network)
for link, (main_path, backup_path) in paths.items():
    print(f'For link {link}, main path is {main_path}, backup path is {backup_path}.')

该代码使用 Python 实现 Dijkstra 算法，并应用于网络主备份路径规划。代码示例包括路径有效性检查和路径获取函数。

使用方法：

1. 将代码保存为 .py 文件（例如 network_path_planning.py）。
2. 在同一目录下创建两个 Excel 文件：物理网络1.xls 和 逻辑网络1.xls，分别存储物理网络和逻辑网络的信息。
3. 运行代码：python network_path_planning.py。

代码将输出每个链接的备用路径信息。

注意：

• 确保 Excel 文件路径正确。
• 物理网络1.xls 和 逻辑网络1.xls 文件应该包含网络连接信息，例如节点之间的连接权重。
• 代码中的 check_validity 函数用于检查备用路径的有效性，并确保备用路径满足特定条件。

扩展：

• 可以根据实际需求修改代码，例如增加对网络节点和连接信息的读取方式，以及路径有效性检查条件。
• 可以将代码集成到更复杂的网络管理系统中，实现自动化的路径规划和管理。