楔子
最短路径是很经典的一个问题，最初看到该类问题时毫无思路，而一旦抓到解题思路的主脉络后，则会惊叹于组织结构化数据的精巧！
问题
a、b、c、d、e、f、g是七个城镇，它们之间的连线表示汽车行驶路线，而连线上的箭头表示道路允许方向。（比如，a和c之间，箭头由a指向c，表示可以开车从a行驶到c；反之，从c直接行驶到a是不行的）问题，找出一条从A镇到G镇途径镇子最少的路线。
思路
解决问题的思路是这样的：
步骤1
从节点a开始，查找可直接到达的节点，也就是节点e和c，姑且把它们称之为一级节点。
一级节点（e、c）中是否有终点g？很显然没有，那么从e、c开始，继续查找。
步骤2
- 从节点e开始好了，它可直达的节点是d、a、f（二级节点），其中是否有终点g？依然没有。
- 节点c可直达的节点还是f（二级节点），也不是终点g。
接下来怎么做？猜到了吧——查看三级节点！等等，我闻到了递归的味道。
步骤3
避免忘记，我将步骤2时代的二级节点d、a、f标注颜色了。
从节点d开始，可直达节点g……hold on！其它的不用管了，我们已经找到了终点g，路径为a->e->d->g。 关键
思路不难理解，接下来的工作就是将上述思路翻译成代码思维，关键点有三。
- point1 队列
回顾下整个查找过程，从起点a的直达节点一级节点，到一级节点下的二级节点，再到二级节点下的三级节点……每步骤下来，有明确的先后次序。那什么数据结构用来处理这种次序呢？FIFO（First In First Out）队列！
从起点a开始，遍历查找它的一级节（e、c）点中是否有终点g，有就开香槟庆祝，没有则将这些节点放入到队列中；然后从队列中获取这些一级节点（e、c），遍历查找它们的可直达节点（二级节点），依然是“有就开香槟庆祝，没有则将这些节点放入到队列中”……
- point2 递归
这个不多说了，前面的 步骤 2 和上面的 point 1 都流露出递归的痕迹，细细体会一下。
- point3 重复节点
前面的分析中，有一个问题被轻易的略过了。
起点a的直达节点中有节点e，节点e的直达节点中也有节点a，它俩你中有我我中有你固然亲密无间，但放任不管的话就陷入死循环了。
所以还要有一个去重机制，这里我选择了用一个Set集合记录放入队列节点的方式进行去重。
代码
ok，最后将前面的各种分析形成代码。
Node节点
其实就是bean，对节点数据进行封装。
用到了lombok，挺好用的工具，感兴趣的朋友自行研究下。 import lombok.Data;/** * @description: 封装节点数据 * @author: liuzijian * @date: 2018-04-11 23:06 */@Datapublic class Node { private String node; private String path; //保存路径 public Node(String node) { this.node = node; path = node; } private final String nextSymbol = "->"; //间隔符 public String pathAppend(String lastPath){ return lastPath + nextSymbol + node; }} ShortestPath算法
用到了guava中的ImmutableList，也是极好用的东西，推荐！
import com.evolution.algorithm.bean.Node;import com.google.common.collect.ImmutableList;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Set;/** * @description: 最短路径问题 * @author: liuzijian * @date: 2018-04-11 23:04 */public class ShortestPath { Map > pic = new HashMap<>(); //存储图 Set existsNodes = new HashSet<>(); //节点去重 LinkedList pathList = new LinkedList<>(); //FIFO队列 /** * 图的初始化 */ private void initPic(){ pic.put("a",ImmutableList.of(new Node("c"),new Node("e"))); pic.put("b",ImmutableList.of(new Node("a"),new Node("g"))); pic.put("c",ImmutableList.of(new Node("f"))); pic.put("d",ImmutableList.of(new Node("a"),new Node("g"))); pic.put("e",ImmutableList.of(new Node("d"),new Node("a"),new Node("f"))); pic.put("f",ImmutableList.of(new Node("b"),new Node("d"))); pic.put("g",ImmutableList. of()); } /** * 构造块中进行图的初始化工作 */ public ShortestPath(){ initPic(); } /** * 路径查找方法的重载 * 为调用方便，将参数source由 Node类型重载为 String类型 */ public void findPath(String source,final String target){ findPath(new Node(source),target); } /** * 核心方法，路径查找 */ private void findPath(Node source,final String target){ List relations = pic.get(source.getNode()); for(Node node:relations){ if(node.getNode().equals(target)){ System.out.println("Get it!Path is '"+node.pathAppend(source.getPath())+"'"); return; }else if(existsNodes.contains(node.getNode())){ //do nothing }else{ existsNodes.add(node.getNode()); pathList.add(node); node.setPath(node.pathAppend(source.getPath())); } } if(pathList.isEmpty()){ System.out.println("Sorry!Can not reach!"); }else{ Node node = pathList.removeFirst(); findPath(node,target); } } public static void main(String[] args) { ShortestPath sp = new ShortestPath(); sp.findPath("d","f"); }} 后序
近期比较痴迷Guava，之前总是对它一知半解的。最近两天有幸拜读公司大神同事，用Guava Cache作本地缓存的代码，敬畏不已！遂决定潜心研究之并写文章记录，敬请期待。