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

这篇博客文章介绍了如何使用Python实现基于图的逻辑网络和物理网络路径规划算法。文章中使用了Dijkstra算法和广度优先搜索算法来寻找最优路径和备用路径，并详细解释了代码的实现过程。

主要功能：

读取逻辑网络和物理网络数据
使用广度优先搜索算法寻找节点数最少的路径
使用Dijkstra算法寻找最大负载路径作为备用路径
删除备用路径上的所有边以避免资源冲突

代码解释：

首先，代码读取逻辑网络和物理网络数据，并存储为numpy数组。
然后，代码定义了两个辅助函数：dijkstra和bfs，分别用于实现Dijkstra算法和广度优先搜索算法。
接下来，代码遍历所有逻辑网络中的节点对，如果节点对之间存在连接，则使用bfs函数寻找节点数最少的路径，并使用dijkstra函数寻找最大负载路径作为备用路径。
最后，代码删除备用路径上的所有边，以避免资源冲突。

注意事项：

代码中的逻辑网络和物理网络数据存储在excel文件中，文件名为'逻辑网络1.xls'和'物理网络1.xls'。
代码中的节点编号从0开始。
代码中的负载代表网络边的容量。

希望这篇文章能够帮助您理解如何使用Python实现基于图的逻辑网络和物理网络路径规划算法。