寻求比skimage.graph.route_through_array更优的路径查找实现方案

原代码使用skimage.graph.route_through_array（基于Dijkstra算法）在小图像上表现正常，但大尺寸图像下效率不足。以下是基于A*算法并采用欧几里得启发式的优化实现，保持与原代码一致的输入输出格式：

import numpy as np
import heapq

def shortest_path(start, end, binary):
    # 定义八邻域（与原代码fully_connected=True一致）
    neighbors = [(-1, -1), (-1, 0), (-1, 1),
                 (0, -1),          (0, 1),
                 (1, -1),  (1, 0), (1, 1)]
    
    # 初始化代价矩阵：可行区域（binary为True）代价1，不可行区域代价1000
    costs = np.where(binary, 1, 1000)
    rows, cols = costs.shape
    
    # 起点和终点坐标转为元组
    start = tuple(start)
    end = tuple(end)
    
    # 欧几里得启发式函数：计算当前点到终点的直线距离
    def heuristic(node):
        return np.sqrt((node[0] - end[0])**2 + (node[1] - end[1])**2)
    
    # 初始化A*所需数据结构
    open_heap = []
    heapq.heappush(open_heap, (0 + heuristic(start), 0, start))  # (f值, g值, 节点)
    came_from = {}
    g_score = {start: 0}
    
    while open_heap:
        current_f, current_g, current_node = heapq.heappop(open_heap)
        
        # 到达终点，回溯路径
        if current_node == end:
            path = []
            while current_node in came_from:
                path.append(current_node)
                current_node = came_from[current_node]
            path.append(start)
            path.reverse()
            return np.array(path), current_g
        
        # 遍历所有邻域节点
        for dy, dx in neighbors:
            neighbor = (current_node[0] + dy, current_node[1] + dx)
            # 检查邻域是否在图像范围内
            if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols:
                # 计算从起点到邻域节点的新g值
                new_g = current_g + costs[neighbor]
                # 如果邻域节点未被访问，或者新g值更小，则更新
                if neighbor not in g_score or new_g < g_score[neighbor]:
                    g_score[neighbor] = new_g
                    f_score = new_g + heuristic(neighbor)
                    heapq.heappush(open_heap, (f_score, new_g, neighbor))
                    came_from[neighbor] = current_node
    
    # 若未找到路径（与原代码行为一致）
    return None, float('inf')

关键说明： #

• 启发式选择：使用欧几里得距离作为启发值，符合A*算法对可采纳启发式的要求（不会高估实际代价），能有效引导搜索向终点方向推进，大幅减少大图像下的搜索节点数量。
• 邻域处理：保持与原代码一致的八邻域搜索（fully_connected=True），确保路径结果的兼容性。
• 代价逻辑：完全沿用原代码的代价规则，可行区域代价为1，障碍区域代价设为1000，保证路径偏好与原实现一致。
• 效率优化：通过优先队列（heapq）高效获取当前f值最小的节点，配合启发式剪枝，相比Dijkstra算法在大图像场景下能显著提升速度。

内容的提问来源于stack exchange，提问作者iarad55