k-shortest-paths 最短路径算法实现 k最短路径算法是一种求解图中最短路径问题的算法，它可以找到图中从起始点到终点的前k短路径。下面是一个实现k最短路径算法的示例代码： ```python import heapq class Graph: def __init__(self, vertices):.. 已关注

提示信息
已关注
k-shortest-paths 最短路径算法实现
k最短路径算法是一种求解图中最短路径问题的算法，它可以找到图中从起始点到终点的前k短路径。下面是一个实现k最短路径算法的示例代码： ```python import heapq class Graph: def __init__(self, vertices): self.vertices = vertices self.edges = [[] for _ in range(vertices)] def add_edge(self, src, dest, weight): self.edges[src].append((dest, weight)) def k_shortest_paths(self, src, dest, k): min_heap = [(0, src, [src])] heapq.heapify(min_heap) shortest_paths = [] while min_heap: cost, vertex, path = heapq.heappop(min_heap) if vertex == dest: shortest_paths.append((cost, path)) if len(shortest_paths) == k: return shortest_paths for neighbor, weight in self.edges[vertex]: if neighbor not in path: new_cost = cost + weight new_path = path + [neighbor] heapq.heappush(min_heap, (new_cost, neighbor, new_path)) return shortest_paths # 示例用法 g = Graph(4) g.add_edge(0, 1, 1) g.add_edge(0, 2, 4) g.add_edge(1, 2, 2) g.add_edge(1, 3, 5) g.add_edge(2, 3, 1) shortest_paths = g.k_shortest_paths(0, 3, 3) for cost, path in shortest_paths: print("Path:", path) print("Cost:", cost) print() ``` 运行上述代码，将输出前三条从起始点到终点的最短路径。
  • 12
  • 文章
  • 0
  • 关注人数
作者/活跃用户
每天快乐一点罂粟甘心妥协岚风殇序曲终一尾流莺浓郁花香水晶花之雨游客甲直来直往意乱
相关站点
关联标签