### 创建加权无向图并查找 K 条最短路径 为了实现创建一个包含 300 个节点的带权无向图，并使用 A* 算法找到 k 条最短路径的目标，可以按照如下方法进行： #### 导入必要的库 首先导入所需的 Python 库 `networkx` 和 `numpy`。 ```python import numpy as np import networkx as nx from heapq import heappop, heappush ``` #### 构建图形结构 定义函数用于构建具有随机权重的完全连通无向图。这里假设每条边都有一个正整数作为其权重。 ```python def generate_weighted_graph(num_nodes=300): """Generates a fully connected undirected graph with random weights.""" # Create an empty Graph object. G = nx.Graph() # Add all possible edges between pairs of vertices. for u in range(num_nodes): for v in range(u + 1, num_nodes): weight = np.random.randint(1, 20) # Random integer from 1 to 19 inclusive. G.add_edge(u, v, weight=weight) return G ``` #### 实现 A* 搜索算法 下面是一个简单的基于优先队列版本的 A* 搜索算法实现，该算法能够返回从起点到终点的最佳路径以及相应的成本。 ```python def astar_search(graph, start_node, goal_node): """Performs A* search on the provided graph.""" open_list = [] closed_set = set() came_from = {} g_score = {node: float('inf') for node in graph.nodes} f_score = {node: float('inf') for node in graph.nodes} g_score[start_node] = 0 f_score[start_node] = heuristic(start_node, goal_node) heappush(open_list, (f_score[start_node], start_node)) while open_list: _, current = heappop(open_list) if current == goal_node: break closed_set.add(current) for neighbor in graph.neighbors(current): tentative_gscore = g_score[current] + graph.edges[(current, neighbor)]['weight'] if neighbor not in closed_set or tentative_gscore < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_gscore f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal_node) if neighbor not in [item[1] for item in open_list]: heappush(open_list, (f_score[neighbor], neighbor)) path = reconstruct_path(came_from, start_node, goal_node) cost = sum([graph.edges[path[i], path[i+1]]['weight'] for i in range(len(path)-1)]) return path, cost def heuristic(node_a, node_b): """Heuristic function estimating distance between two points""" pos_a = get_position_of_node(node_a) pos_b = get_position_of_node(node_b) return abs(pos_a - pos_b) def get_position_of_node(node_id): """Returns position associated with each node ID. For simplicity this returns just the id itself.""" return node_id def reconstruct_path(came_from, start, end): """Reconstructs the optimal path found by A*. """ reversed_path = [end] while end != start: end = came_from[end] reversed_path.append(end) return list(reversed(reversed_path)) ``` #### 查找多条次优路径 要获取多个不同的解，则可以在每次迭代过程中记录下当前最优解之后再将其对应的边暂时删除掉，从而强迫后续搜索走其他路线；当完成一次完整的遍历后再恢复这些被删去的连接关系以便不影响下次调用的结果准确性[^4]. ```python def find_k_shortest_paths(graph, source, target, k=5): """Finds up to 'k' distinct shortest paths using modified version of Dijkstra's algorithm""" results = [] original_edges = dict(graph.edges()) try: for _ in range(k): path, cost = astar_search(graph, source, target) results.append((path, cost)) # Temporarily remove used edges so next iteration finds alternative routes removed_edges = [(u, v) for u, v in zip(path[:-1], path[1:])] for edge in removed_edges: del graph[edge[0]][edge[1]] finally: # Restore any changes made during execution regardless whether exception occurred or not graph.clear_edges() graph.add_edges_from(original_edges.items()) return results[:k] ``` 上述代码片段展示了如何通过修改后的Dijkstra/A*算法来计算给定源点至目标点间的前几条不同路径的方法之一。值得注意的是，在实际应用中可能还需要考虑更多因素比如性能优化等问题.