yen算法求k短路代码

以下是基于 Dijkstra 算法的 Yen 算法求 k 短路的 Python 代码实现：

from queue import PriorityQueue
from collections import defaultdict

def dijkstra(graph, start, end=None):
    # 初始化距离和前驱节点
    distance = {start: 0}
    predecessor = {start: None}
    # 初始化优先队列，按距离排序
    pq = PriorityQueue()
    pq.put((0, start))

    while not pq.empty():
        # 取出距离最小的节点
        curr_dist, curr_node = pq.get()

        # 如果已经到达终点，则返回到达终点的距离和路径
        if end is not None and curr_node == end:
            path = []
            while curr_node is not None:
                path.append(curr_node)
                curr_node = predecessor[curr_node]
            path.reverse()
            return curr_dist, path

        # 遍历当前节点的所有邻居节点
        for neighbor, weight in graph[curr_node].items():
            # 计算到邻居节点的距离
            new_dist = curr_dist + weight
            # 更新邻居节点的距离和前驱节点
            if neighbor not in distance or new_dist < distance[neighbor]:
                distance[neighbor] = new_dist
                predecessor[neighbor] = curr_node
                pq.put((new_dist, neighbor))

    # 如果没有到达终点，则返回起点到所有节点的距离和前驱节点
    return distance, predecessor

def yen_k_shortest_paths(graph, start, end, k):
    # 初始化最短路径和备选路径
    A = [(None, [start])]
    B = PriorityQueue()

    for k in range(1, k+1):
        # 遍历备选路径
        for i in range(len(A[-1][1])-1):
            # 切断备选路径中的边
            spur_node = A[-1][1][i]
            root_path = A[-1][1][:i+1]

            # 构建新的图
            subgraph = defaultdict(dict)
            for path_dist, path in A:
                if root_path == path[:i+1]:
                    src = path[i]
                    dst = path[i+1]
                    subgraph[src][dst] = graph[src][dst]

            for node in root_path:
                if node != spur_node:
                    # 移除所有与 spur_node 相邻的节点
                    for neighbor in subgraph[spur_node]:
                        del subgraph[neighbor][spur_node]
                    del subgraph[spur_node]

                    # 执行 Dijkstra 算法，计算 spur_node 到所有节点的最短路径
                    spur_path_dist, spur_path = dijkstra(subgraph, spur_node, end)

                    if spur_path is not None:
                        # 将 spur_path 和 root_path 合并成一条路径
                        total_path = root_path[:-1] + spur_path

                        # 计算总距离
                        total_dist = 0
                        for j in range(len(total_path)-1):
                            total_dist += graph[total_path[j]][total_path[j+1]]

                        # 将新路径加入备选路径
                        B.put((total_dist, total_path))

            # 如果没有更多备选路径，则退出循环
            if B.empty():
                break

        # 如果没有更多备选路径，则退出循环
        if B.empty():
            break

        # 选择距离最短的路径作为最新的最短路径
        shortest_dist, shortest_path = B.get()
        A.append((shortest_dist, shortest_path))

    # 返回前 k 条最短路径
    return [path for dist, path in A[:k]]

其中，`graph` 是一个字典，表示图中的邻接矩阵。例如，`graph[src][dst]` 表示从 `src` 到 `dst` 的边权重。`start` 和 `end` 分别表示起点和终点。`k` 表示求前 k 条最短路径。函数 `yen_k_shortest_paths` 返回前 k 条最短路径的列表，每个路径都是一个节点列表。