针对有权有向图，计算两点之间的最短路径

• 计算地图上两点间距离最短
• 计算地图上两点间红灯最少

• 算法逻辑

1. 步骤
   • 构建小顶堆
   • 取堆顶元素，到所有可能的路径的距离最短的路径为下一个
   • 递归调用
2. 主要变量
   • predecessor 前驱节点列表用于输出路径
   • queue 小顶堆
   • inqueue 访问队列

• 解决实际问题首先建模

• 描述：A算法是对Dijkstra算法的优化，Dijkstra是广度搜索，没有考虑顶点到终点的距离，A主要优化这个方面

1. 优化方式：
   • 添加了h启发函数（heuristic function）f(i)=g(i)+h(i)，构建优先队列以f(i)构建
   • 曼哈顿距离：md=(v1.x-v2.x)+(v1.y-v2.y),利用曼哈顿距离做启发函数提高效率
   • 更新顶点距离时，同时更新f(i)的值
   • 循环结束的条件也不同，Dijkstra算法是终点出优先级队列的时候结束，A*算法只要遍历到终点就结束

对于最短路径方式，最简单的方式是回溯穷举找出最小的，但是鉴于执行效率，可以采取动态规划的Dijkstra算法进行剪枝，虽然采用了 动态规划，但是还是要遍历后序所有顶点，来确定最短路径，A*通过启函数缩小遍历范围，只要遍历到终点即为完成，搜索出的路径不一定 是最短路径，但是在执行效率上大大提升，效率和效果上达到平衡的状态，所以在日常中较为常用。