Python实现网络路径选择算法：寻找最短路径和备用路径

import numpy as np
import pandas as pd
from collections import deque
import heapq

# 读取网络数据
logicalNetwork = pd.read_excel('逻辑网络1.xls', header=None).to_numpy()
physicalNetwork = pd.read_excel('物理网络1.xls', header=None).to_numpy()

# 获取网络的节点数
num_nodes = logicalNetwork.shape[0]

# 用于存储已经存在的路径
existing_paths = set()

# 用于Dijkstra搜索的辅助函数
def dijkstra(source, target, graph):
    # 初始化优先队列，格式为(最小负载，当前节点，路径)
    queue = [(-graph[source].max(), source, [source])]
    # 初始化一个集合存储已经访问过的节点
    visited = set([source])
    while queue:
        min_load, node, path = heapq.heappop(queue)
        min_load = -min_load  # 因为Python的heapq是最小堆，所以我们存储负载的相反数，使得负载最大的路径优先出队
        if node == target:
            return [n+1 for n in path]  # 返回的路径节点编号要加1，因为我们的节点编号是从0开始的
        for next_node, next_load in enumerate(graph[node]):
            if next_node not in visited and next_load >= min_load:
                heapq.heappush(queue, (-next_load, next_node, path + [next_node]))
                visited.add(next_node)
    return []

# 用于广度优先搜索的辅助函数
def bfs(source, target):
    queue = deque([[source]])
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == target:
            return [n+1 for n in path]
        for next_node, next_load in enumerate(physicalNetwork[node]):
            if next_load > 0 and next_node not in path:
                queue.append(path + [next_node])
    return []

# 遍历所有逻辑网络中的节点对
for i in range(num_nodes):
    for j in range(i+1, num_nodes):
        if logicalNetwork[i, j] != 0:  # 如果逻辑网络中的节点对是直接连接的
            # 使用BFS找到节点数最少的路径
            path = bfs(i, j)
            print(f'From node {i+1} to node {j+1}, path is {path}')

            #创建物理网络的副本
            physicalNetwork_copy = physicalNetwork.copy()

            # 使用Dijkstra搜索找到备用路径
            path2 = dijkstra(i, j, physicalNetwork_copy)
            print(f'From node {i+1} to node {j+1}, alternate path is {path2}')

            # 删除备用路径上的所有边
            for k in range(len(path2) - 1):
                physicalNetwork[path2[k]-1, path2[k+1]-1] = 0

这段代码实现了一个网络路径选择算法，根据给定的逻辑网络和物理网络，找到逻辑网络中所有节点对之间的最短路径和备用路径。

算法流程：

读取网络数据: 从Excel文件中读取逻辑网络和物理网络的拓扑结构数据。
遍历逻辑网络节点对: 遍历逻辑网络中的所有节点对，查找需要计算路径的节点对。
使用BFS寻找最短路径: 对于每个需要计算路径的节点对，使用广度优先搜索（BFS）算法在物理网络中找到节点数最少的路径。
使用Dijkstra算法寻找备用路径: 创建物理网络的副本，并使用Dijkstra算法在副本上找到备用路径。搜索备用路径时，会排除已经使用的边，以确保找到的是不同的路径。
删除备用路径上的边: 为了避免重复使用备用路径，将备用路径上的边从物理网络中删除。

代码解释：

logicalNetwork: 逻辑网络的邻接矩阵，表示逻辑网络中节点之间的连接关系。
physicalNetwork: 物理网络的邻接矩阵，表示物理网络中节点之间的连接关系和负载信息。
bfs(source, target): 使用广度优先搜索算法查找从源节点 source 到目标节点 target 的节点数最少的路径。
dijkstra(source, target, graph): 使用Dijkstra算法在图 graph 中查找从源节点 source 到目标节点 target 的负载最大的路径。

代码优势：

使用BFS和Dijkstra算法，能够高效地找到最短路径和备用路径。
代码结构清晰，易于理解和维护。
通过删除备用路径上的边，可以避免路径重复使用，提高网络资源利用率。

如果您有任何关于网络路径选择算法的问题，欢迎留言讨论。