k路最短路径算法python代码实现

以下是K路最短路径算法的Python代码实现，其中使用了Dijkstra算法来找到单源最短路径。

import heapq

def k_shortest_paths(graph, start, end, k):
    paths = []
    shortest_path = dijkstra(graph, start, end)
    paths.append(shortest_path)

    for i in range(1, k):
        graph_copy = graph.copy()
        for j in range(len(paths[-1])-1):
            node1, node2 = paths[-1][j], paths[-1][j+1]
            if node1 in graph_copy and node2 in graph_copy[node1]:
                del graph_copy[node1][node2]
        if not graph_copy:
            break
        path = dijkstra(graph_copy, start, end)
        if path not in paths:
            paths.append(path)

    return paths

def dijkstra(graph, start, end):
    heap = [(0, start, [])]
    while heap:
        (cost, node, path) = heapq.heappop(heap)
        if node not in path:
            path = path + [node]
            if node == end:
                return path
            for next_node in graph.get(node, {}):
                heapq.heappush(heap, (cost + graph[node][next_node], next_node, path))
    return None

其中，`graph` 是一个字典，用来表示图的邻接表，`start` 和 `end` 分别表示起点和终点，`k` 表示要求的第 k 短路径。返回的结果是一个列表，包含 k 条路径，每条路径是一个节点列表。