### Python 船舶路径规划示例程序 以下是基于Dijkstra算法的一个简单船舶路径规划的Python示例程序。此程序模拟了一个简单的二维网格地图，其中节点表示可能的位置，边权值代表航行成本（如距离或时间）。为了便于理解，关键参数和算法位置已进行了详细的标注。 ```python import heapq import networkx as nx import matplotlib.pyplot as plt # 定义地图边缘列表，每个元素是一个三元组(起点, 终点, 权重) edges = [ ('Port_A', 'Point_B', 5), # Port_A到Point_B的距离为5 ('Port_A', 'Point_C', 9), # Port_A到Point_C的距离为9 ('Point_B', 'Point_D', 2), # Point_B到Point_D的距离为2 ('Point_C', 'Point_D', 4), # Point_C到Point_D的距离为4 ('Point_D', 'Destination_E', 3) # Point_D到Destination_E的距离为3 ] # 创建无向图G并添加带权重的边 G = nx.Graph() G.add_weighted_edges_from(edges) def dijkstra_algorithm(graph, start_node): """ 实现Dijkstra算法以找到最短路径。 参数: graph: NetworkX 图对象 start_node: 起始节点名称 返回: distances: 所有点到起始点的最短距离字典 previous_nodes: 前驱节点字典，用于重建路径 """ unvisited_nodes = list(graph.nodes()) # 初始化未访问节点集合 shortest_path = {} # 存储当前最短路径长度 previous_nodes = {} # 存储前驱节点以便回溯路径 max_value = float('inf') for node in unvisited_nodes: shortest_path[node] = max_value # 将所有节点初始化为无穷大 shortest_path[start_node] = 0 # 起始节点设为0 while unvisited_nodes: current_min_node = None # 寻找当前最小距离节点 for node in unvisited_nodes: # 遍历剩余节点找出最近者 if current_min_node is None or shortest_path[node] < shortest_path[current_min_node]: current_min_node = node neighbors = graph.neighbors(current_min_node) # 获取邻居节点 weight_to_neighbors = graph.edges[current_min_node, neighbor]['weight'] # 当前节点到邻居的权重 for neighbor in neighbors: # 更新邻居节点的距离 tentative_value = shortest_path[current_min_node] + weight_to_neighbors if tentative_value < shortest_path[neighbor]: # 如果发现更短路径则更新 shortest_path[neighbor] = tentative_value previous_nodes[neighbor] = current_min_node # 设置前驱节点 unvisited_nodes.remove(current_min_node) # 移除已经处理过的节点 return shortest_path, previous_nodes start_port = 'Port_A' # 设定起始港口 destination = 'Destination_E' # 设定目标目的地 shortest_distances, path_reconstruction = dijkstra_algorithm(G, start_port) # 输出最短路径及其距离 path = [] step = destination while step != start_port: path.append(step) step = path_reconstruction.get(step) path.append(start_port) path.reverse() print(f"从{start_port}到{destination}的最短路径为: {' -> '.join(path)}") print(f"总航程为: {shortest_distances[destination]}") # 可视化图形展示 pos = nx.spring_layout(G) plt.figure(figsize=(10, 8)) nx.draw(G, pos, with_labels=True, node_size=500, node_color="lightblue", alpha=0.6) labels = nx.get_edge_attributes(G, 'weight') nx.draw_networkx_edge_labels(G, pos, edge_labels=labels) # 加亮显示最短路径上的边 edge_list = [(path[i], path[i+1]) for i in range(len(path)-1)] nx.draw_networkx_edges(G, pos, edgelist=edge_list, edge_color='r', width=2) plt.title("Vessel Path Planning Using Dijkstra Algorithm") plt.show() ``` #### 关键参数说明 - **`edges`**: 表示地图中的连接关系以及每条航线的成本[^1]。 - **`dijkstra_algorithm`函数**: 这里实现了经典的Dijkstra算法来求解最短路径问题。 - **`start_port` 和 `destination`**: 用户可以根据实际需求修改这两个变量以指定不同的出发港和目的港[^1]。 --- ###