当前位置：首页 > news >正文

图论最短路径：Dijkstra 与 A* 的工程应用对比与实现

news 2026/6/17 15:54:11

图论最短路径：Dijkstra 与 A* 的工程应用对比与实现

一、最短路径的"选择困难"：Dijkstra 够用吗？A* 一定更快吗？

最短路径是图论中应用最广的问题，但 Dijkstra 和 A* 的选择并不简单。Dijkstra 是无信息搜索，保证找到全局最短路径；A* 是启发式搜索，在有好的启发函数时远快于 Dijkstra，但启发函数设计不当可能导致结果不最优或性能更差。

面试中，最短路径问题几乎必考。但面试官考察的不仅是"能不能写出 Dijkstra"，更是"知不知道什么时候该用 A*，什么时候不该用"。理解两种算法的适用边界，比背诵代码更重要。

二、算法原理与对比

graph TB subgraph Dijkstra A[优先队列<br/>按实际距离排序] --> B[逐层扩展<br/>无方向偏好] B --> C[保证全局最优<br/>探索范围大] end subgraph A星 D[优先队列<br/>按f=g+h排序] --> E[启发式引导<br/>朝目标方向扩展] E --> F[启发函数好→快<br/>启发函数差→慢或不优] end subgraph 关键差异 G[Dijkstra: f = g<br/>仅看已走距离] H[A*: f = g + h<br/>已走距离+估计剩余] I[h满足一致性→结果最优] end

A* 的核心改进是将"到目标的估计距离 h(n)"加入优先队列的排序依据。当 h(n) 是到目标的下界（即 h(n) ≤ 实际最短距离）时，A* 保证找到最短路径；当 h(n) = 0 时，A* 退化为 Dijkstra。

三、算法实现

3.1 Dijkstra 实现

import heapq from typing import Dict, List, Tuple def dijkstra( graph: Dict[int, List[Tuple[int, float]]], start: int ) -> Tuple[Dict[int, float], Dict[int, int]]: """ Dijkstra 最短路径算法 graph: 邻接表 {节点: [(邻居, 权重), ...]} start: 起点 返回: (最短距离表, 前驱节点表) """ dist = {start: 0.0} prev = {} # 优先队列：(距离, 节点) pq = [(0.0, start)] visited = set() while pq: d, u = heapq.heappop(pq) if u in visited: continue visited.add(u) for v, weight in graph.get(u, []): if v in visited: continue new_dist = d + weight if new_dist < dist.get(v, float('inf')): dist[v] = new_dist prev[v] = u heapq.heappush(pq, (new_dist, v)) return dist, prev def reconstruct_path(prev: Dict[int, int], target: int) -> List[int]: """从前驱表重建路径""" path = [] current = target while current in prev: path.append(current) current = prev[current] path.append(current) return path[::-1]

3.2 A* 实现

from typing import Callable def astar( graph: Dict[int, List[Tuple[int, float]]], start: int, goal: int, heuristic: Callable[[int, int], float] ) -> Tuple[float, List[int]]: """ A* 最短路径算法 heuristic: 启发函数 h(n, goal)，必须满足 h(n) ≤ 实际最短距离 返回: (最短距离, 路径) """ # g_score: 起点到 n 的实际最短距离 g_score = {start: 0.0} # f_score: g_score + heuristic f_score = {start: heuristic(start, goal)} # 优先队列按 f_score 排序 open_set = [(f_score[start], start)] came_from = {} closed_set = set() while open_set: _, current = heapq.heappop(open_set) if current == goal: # 重建路径 path = [current] while current in came_from: current = came_from[current] path.append(current) return g_score[goal], path[::-1] if current in closed_set: continue closed_set.add(current) for neighbor, weight in graph.get(current, []): if neighbor in closed_set: continue tentative_g = g_score[current] + weight if tentative_g < g_score.get(neighbor, float('inf')): came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + heuristic(neighbor, goal) heapq.heappush(open_set, (f_score[neighbor], neighbor)) return float('inf'), [] # 不可达

3.3 启发函数设计

import math def manhattan_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float: """曼哈顿距离：适用于网格移动（只能上下左右）""" return abs(a[0] - b[0]) + abs(a[1] - b[1]) def euclidean_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float: """欧几里得距离：适用于自由移动""" return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2) def chebyshev_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float: """切比雪夫距离：适用于8方向移动""" return max(abs(a[0] - b[0]), abs(a[1] - b[1])) # 地图坐标到节点ID的映射 coord_to_id = {} # {(x, y): node_id} id_to_coord = {} # {node_id: (x, y)} def grid_heuristic(node_id: int, goal_id: int) -> float: """网格地图的启发函数""" a = id_to_coord[node_id] b = id_to_coord[goal_id] return manhattan_distance(a, b)