目录

Python实例题

题目

要求：

解题思路：

代码实现：

Python实例题

题目

基于 Dijkstra 算法的地图导航系统

要求：

• 实现一个简单的地图导航系统，使用 Dijkstra 算法计算最短路径。
• 支持以下功能：
  • 加载地图数据（节点和边）
  • 计算两点之间的最短路径
  • 可视化地图和路径
  • 支持不同的权重计算方式（距离、时间、费用）
• 添加用户交互界面，允许用户选择起点和终点。

解题思路：

• 使用邻接表表示地图图结构。
• 实现 Dijkstra 算法计算最短路径。
• 使用 NetworkX 和 Matplotlib 进行地图可视化。

代码实现：

import networkx as nx
import matplotlib.pyplot as plt
import heapq

class MapGraph:
    def __init__(self):
        self.graph = nx.Graph()
    
    def add_node(self, node_id, label=None, pos=None):
        """添加地图节点"""
        self.graph.add_node(node_id, label=label or str(node_id), pos=pos)
    
    def add_edge(self, node1, node2, weight=1, **kwargs):
        """添加地图边"""
        self.graph.add_edge(node1, node2, weight=weight, **kwargs)
    
    def dijkstra(self, start, end, weight='weight'):
        """Dijkstra算法实现"""
        distances = {node: float('inf') for node in self.graph.nodes}
        distances[start] = 0
        
        priority_queue = [(0, start)]
        previous_nodes = {node: None for node in self.graph.nodes}
        
        while priority_queue:
            current_dist, current_node = heapq.heappop(priority_queue)
            
            if current_node == end:
                break
            
            if current_dist > distances[current_node]:
                continue
            
            for neighbor in self.graph.neighbors(current_node):
                weight_val = self.graph[current_node][neighbor].get(weight, 1)
                distance = current_dist + weight_val
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous_nodes[neighbor] = current_node
                    heapq.heappush(priority_queue, (distance, neighbor))
        
        # 构建路径
        path = []
        current_node = end
        
        while current_node is not None:
            path.append(current_node)
            current_node = previous_nodes[current_node]
        
        path.reverse()
        
        if path[0] == start:
            return path, distances[end]
        else:
            return None, None
    
    def visualize(self, path=None, figsize=(10, 8)):
        """可视化地图和路径"""
        plt.figure(figsize=figsize)
        
        # 获取节点位置
        pos = nx.get_node_attributes(self.graph, 'pos')
        if not pos:
            pos = nx.spring_layout(self.graph)
        
        # 绘制节点
        nx.draw_networkx_nodes(
            self.graph, pos, 
            node_size=700, 
            node_color='lightblue', 
            edgecolors='black'
        )
        
        # 绘制节点标签
        labels = nx.get_node_attributes(self.graph, 'label')
        nx.draw_networkx_labels(self.graph, pos, labels, font_size=12)
        
        # 绘制边
        edge_weights = nx.get_edge_attributes(self.graph, 'weight')
        nx.draw_networkx_edges(
            self.graph, pos, 
            width=2, 
            edge_color='gray', 
            alpha=0.6
        )
        
        # 绘制边权重
        nx.draw_networkx_edge_labels(
            self.graph, pos, 
            edge_labels=edge_weights, 
            font_size=10
        )
        
        # 如果有路径，高亮显示
        if path and len(path) > 1:
            path_edges = [(path[i], path[i+1]) for i in range(len(path)-1)]
            
            nx.draw_networkx_edges(
                self.graph, pos, 
                edgelist=path_edges, 
                width=4, 
                edge_color='red', 
                alpha=0.8
            )
            
            # 高亮起点和终点
            nx.draw_networkx_nodes(
                self.graph, pos, 
                nodelist=[path[0]], 
                node_size=700, 
                node_color='green', 
                edgecolors='black'
            )
            
            nx.draw_networkx_nodes(
                self.graph, pos, 
                nodelist=[path[-1]], 
                node_size=700, 
                node_color='red', 
                edgecolors='black'
            )
        
        plt.axis('off')
        plt.title('地图导航系统')
        plt.tight_layout()
        plt.show()

def main():
    # 创建示例地图
    map_graph = MapGraph()
    
    # 添加节点（位置为(x, y)坐标）
    map_graph.add_node('A', '学校', (1, 3))
    map_graph.add_node('B', '医院', (3, 4))
    map_graph.add_node('C', '商场', (4, 2))
    map_graph.add_node('D', '公园', (2, 1))
    map_graph.add_node('E', '酒店', (5, 3))
    map_graph.add_node('F', '图书馆', (6, 1))
    
    # 添加边（距离、时间、费用）
    map_graph.add_edge('A', 'B', distance=2.5, time=10, cost=5)
    map_graph.add_edge('A', 'D', distance=2.0, time=8, cost=4)
    map_graph.add_edge('B', 'C', distance=1.8, time=7, cost=3)
    map_graph.add_edge('B', 'E', distance=3.0, time=12, cost=6)
    map_graph.add_edge('C', 'E', distance=2.2, time=9, cost=4)
    map_graph.add_edge('C', 'F', distance=1.5, time=6, cost=3)
    map_graph.add_edge('D', 'F', distance=4.0, time=15, cost=7)
    map_graph.add_edge('E', 'F', distance=2.8, time=11, cost=5)
    
    print("地图节点:")
    for node_id, data in map_graph.graph.nodes(data=True):
        print(f"{node_id}: {data['label']}")
    
    # 用户交互
    while True:
        print("\n请选择导航模式:")
        print("1. 最短距离")
        print("2. 最短时间")
        print("3. 最低费用")
        print("4. 查看地图")
        print("5. 退出")
        
        choice = input("请输入选项 (1-5): ")
        
        if choice == '5':
            break
        
        if choice == '4':
            map_graph.visualize()
            continue
        
        if choice not in ['1', '2', '3']:
            print("无效的选项，请重新输入。")
            continue
        
        weight_map = {'1': 'distance', '2': 'time', '3': 'cost'}
        weight_type = weight_map[choice]
        weight_name = {'distance': '距离', 'time': '时间', 'cost': '费用'}[weight_type]
        
        start_node = input("请输入起点节点 (A-F): ").upper()
        end_node = input("请输入终点节点 (A-F): ").upper()
        
        if start_node not in map_graph.graph.nodes or end_node not in map_graph.graph.nodes:
            print("无效的节点，请重新输入。")
            continue
        
        path, total_cost = map_graph.dijkstra(start_node, end_node, weight=weight_type)
        
        if path:
            print(f"\n最短{weight_name}路径:")
            path_str = " -> ".join([map_graph.graph.nodes[node]['label'] for node in path])
            print(f"{path_str}")
            print(f"总{weight_name}: {total_cost}")
            
            # 可视化路径
            map_graph.visualize(path)
        else:
            print(f"无法找到从 {start_node} 到 {end_node} 的路径。")

if __name__ == "__main__":
    main()