在求最短路径问题是，如果去除负权边的情况，可以使用Dijkstra算法来替代贝尔曼-福特算法，复杂度更优。接下来介绍的A*算法，也是一种相对更优的算法。看下图：
示意图
使用Dijkstra算法来计算AB的最短路径，基本上要把所有的点、边都遍历，才能得到最短路径——绿线。但是站在人类的角度来看，蓝线是不需要考虑的，因为有个成语叫“南辕北辙”，我们非常清楚地知道，按照蓝线走，哪怕走一步，都离目标B远了。所以在搜索路径的时候，完全可以抛弃蓝线。等于是在众多分支中，“剪”去一条——这就是“剪枝”。
那么按照什么标准“剪”，就很重要了，这里引出下一个概念——估价函数。
正如之前所说，我们之所以“剪”去蓝线，就是因为我们“估计”走蓝线会离目的地的“距离”更大。所以我们可以通过估价函数，先“估”出起点到终点的距离，在搜索路径的时候，如果某条路线距离目的地的距离越来越大，则可以“剪”去。
当然，估值对算法的影响很大。估大了，比如100万公里，去趟月球再绕回来都有富余；估小了，比如1米，那连门都出不了了。
在A*算法中，常用的距离估价函数就是之前写的三个，不再赘述。下面着重讲A*算法。
示意图
如上图，设尽可上下左右移动，距离估价函数使用曼哈顿距离，边权重统一为10，起点8，终点18，10，16，22为障碍物。
我们要对节点进行松弛操作，也就是将节点的权重降至最小。A*算法相比较贝尔曼-福特算法、Dijkstra算法重要的不同之一就是对权重值的计算，函数如下：
权重值f=起点到节点的移动代价g+节点到终点的预估距离h。
A*算法设置两个集合：open——待处理节点、close——已处理节点。
算法描述：
0、初始化open集合，将起点放入open中，权重为0。
1、遍历open集合
1.1、如果open为空则说明搜索完成，跳出。
1.2、不为空，取出权重最小的节点。
1.2.1、节点是终点，跳出。
1.2.2、节点非终点。
1.2.2.1、从open挪入close。
1.2.2.2、遍历节点的临近节点。
1.2.2.2.1、临近节点在close中，跳出。
1.2.2.2.2、临近节点不在open中：
计算起点到临近节点的曼哈顿距离g；计算临近节点到终点的曼哈顿距离h；总距离f=g+h；放入open集合中；修改节点的g、h值；记录父节点。
1.2.2.2.3、临近节点在open中：
获取临近节点原g——tmpG；起点经父节点到临近节点的新距离g=(父g+10)；
如果tmpG<=g，跳出。
如果tmpG>g：临近节点新总距离f=g+原h；放入open集合中；修改临近节点的g值；记录父节点。//这一步就是松弛操作，三个距离f、g、h，使用g作比较，是因为节点到终点的距离H是固定的，G越小，说明起点到节点的距离越小，总距离F就越小。代码如下：
public void getShortestPath(int start, int end) {
// 初始化节点的父节点Map
Map<Integer, Integer> parentMap = Maps.newHashMap();
// 初始化节点路径
Table<Integer, Integer, Integer> ppw = this.buildPPW();
// 初始化节点Map
Map<Integer, Node> nodeMap = this.buildNodeMap();
nodeMap.get(start).setG(0);
nodeMap.get(start).setH(Distance.manhattan(nodeMap.get(start), nodeMap.get(end)).intValue());
// 初始化open集合，将起点放入，权重F为0
Map<Integer, Integer> openMap = Maps.newHashMap();
openMap.put(start, 0);
Map<Integer, Integer> closeMap = Maps.newHashMap();
while (!openMap.isEmpty()) {
// 获取权重值最小的节点
Map.Entry<Integer, Integer> min = this.getMinPoint(openMap);
// 最小权重节点是终点，跳出
if (min.getKey().equals(end)) {
break;
}
// 将最小权重节点从open集合移除，加入close集合
closeMap.put(min.getKey(), min.getValue());
openMap.remove(min.getKey());
// 开始遍历min的临近节点。完全可以采用Map<节点，临近节点List>的数据结构
for (Map.Entry<Integer, Node> entry : nodeMap.entrySet()) {
// 节点不相邻
if (Objects.isNull(ppw.get(min.getKey(), entry.getKey()))) {
continue;
}
// 临近节点在close集合中
if (closeMap.containsKey(entry.getKey())) {
continue;
}
// 临近节点不在open集合中
if (!openMap.containsKey(entry.getKey())) {
// 起点到临近节点的距离
int g = Distance.manhattan(nodeMap.get(min.getKey()), nodeMap.get(entry.getKey())).intValue();
// 临近节点到终点的距离
int h = Distance.manhattan(nodeMap.get(entry.getKey()), nodeMap.get(end)).intValue();
// 起点经临近节点到终点的总距离
int f = g + h;
// 放入open集合
openMap.put(entry.getKey(), f);
// 更改Node的距离值
nodeMap.get(entry.getKey()).setG(g);
nodeMap.get(entry.getKey()).setH(h);
// 记录父节点
parentMap.put(entry.getKey(), min.getKey());
} else {
// 临近节点在open集合中
// 获取临近节点的原权重G
int tmpG = nodeMap.get(entry.getKey()).getG();
// 起点经父节点到临近节点的距离。使用G来作比较，是因为节点到终点的距离H是固定的，G越小，说明起点到节点的距离越小，总距离F就越小
int g = nodeMap.get(min.getKey()).getG() + 10;
// 新值较小
if (tmpG > g) {
// 临近节点到终点的距离
int h = nodeMap.get(entry.getKey()).getH();
// 起点经临近节点到终点的总距离
int f = g + h;
// 放入open集合
openMap.put(entry.getKey(), f);
// 更改Node的距离值
nodeMap.get(entry.getKey()).setG(g);
// 记录父节点
parentMap.put(entry.getKey(), min.getKey());
}
}
}
}
}在代码中，Node就4个属性：坐标x、y；距离h、g——初始值都是Integer.MAX_VALUE。不再赘述。
额外要说的是节点路径集合Table<Integer, Integer, Integer> ppw，这个是我沿用以前的代码，并不优化，大家完全可以构建一个Map<节点,临近节点List>替换。