摘要：楔子最短路徑是很經(jīng)典的一個(gè)問題，最初看到該類問題時(shí)毫無思路，而一旦抓到解題思路的主脈絡(luò)后，則會(huì)驚嘆于組織結(jié)構(gòu)化數(shù)據(jù)的精巧問題是七個(gè)城鎮(zhèn)，它們之間的連線表示汽車行駛路線，而連線上的箭頭表示道路允許方向。

最短路徑是很經(jīng)典的一個(gè)問題，最初看到該類問題時(shí)毫無思路，而一旦抓到解題思路的主脈絡(luò)后，則會(huì)驚嘆于組織結(jié)構(gòu)化數(shù)據(jù)的精巧！

a、b、c、d、e、f、g是七個(gè)城鎮(zhèn)，它們之間的連線表示汽車行駛路線，而連線上的箭頭表示道路允許方向。（比如，a和c之間，箭頭由a指向c，表示可以開車從a行駛到c；反之，從c直接行駛到a是不行的）問題，找出一條從A鎮(zhèn)到G鎮(zhèn)途徑鎮(zhèn)子最少的路線。

解決問題的思路是這樣的：

從節(jié)點(diǎn)a開始，查找可直接到達(dá)的節(jié)點(diǎn)，也就是節(jié)點(diǎn)e和c，姑且把它們稱之為一級(jí)節(jié)點(diǎn)。

一級(jí)節(jié)點(diǎn)（e、c）中是否有終點(diǎn)g？很顯然沒有，那么從e、c開始，繼續(xù)查找。

從節(jié)點(diǎn)e開始好了，它可直達(dá)的節(jié)點(diǎn)是d、a、f（二級(jí)節(jié)點(diǎn)），其中是否有終點(diǎn)g？依然沒有。

節(jié)點(diǎn)c可直達(dá)的節(jié)點(diǎn)還是f（二級(jí)節(jié)點(diǎn)），也不是終點(diǎn)g。

接下來怎么做？猜到了吧——查看三級(jí)節(jié)點(diǎn)！等等，我聞到了遞歸的味道。

避免忘記，我將步驟2時(shí)代的二級(jí)節(jié)點(diǎn)d、a、f標(biāo)注顏色了。
從節(jié)點(diǎn)d開始，可直達(dá)節(jié)點(diǎn)g……h(huán)old on！其它的不用管了，我們已經(jīng)找到了終點(diǎn)g，路徑為a->e->d->g。

思路不難理解，接下來的工作就是將上述思路翻譯成代碼思維，關(guān)鍵點(diǎn)有三。

point1 隊(duì)列

回顧下整個(gè)查找過程，從起點(diǎn)a的直達(dá)節(jié)點(diǎn)一級(jí)節(jié)點(diǎn)，到一級(jí)節(jié)點(diǎn)下的二級(jí)節(jié)點(diǎn)，再到二級(jí)節(jié)點(diǎn)下的三級(jí)節(jié)點(diǎn)……每步驟下來，有明確的先后次序。那什么數(shù)據(jù)結(jié)構(gòu)用來處理這種次序呢？FIFO（First In First Out）隊(duì)列！

從起點(diǎn)a開始，遍歷查找它的一級(jí)節(jié)（e、c）點(diǎn)中是否有終點(diǎn)g，有就開香檳慶祝，沒有則將這些節(jié)點(diǎn)放入到隊(duì)列中；然后從隊(duì)列中獲取這些一級(jí)節(jié)點(diǎn)（e、c），遍歷查找它們的可直達(dá)節(jié)點(diǎn)（二級(jí)節(jié)點(diǎn)），依然是“有就開香檳慶祝，沒有則將這些節(jié)點(diǎn)放入到隊(duì)列中”……

point2 遞歸

這個(gè)不多說了，前面的 步驟 2 和上面的 point 1 都流露出遞歸的痕跡，細(xì)細(xì)體會(huì)一下。

point3 重復(fù)節(jié)點(diǎn)

前面的分析中，有一個(gè)問題被輕易的略過了。

起點(diǎn)a的直達(dá)節(jié)點(diǎn)中有節(jié)點(diǎn)e，節(jié)點(diǎn)e的直達(dá)節(jié)點(diǎn)中也有節(jié)點(diǎn)a，它倆你中有我我中有你固然親密無間，但放任不管的話就陷入死循環(huán)了。

所以還要有一個(gè)去重機(jī)制，這里我選擇了用一個(gè)Set集合記錄放入隊(duì)列節(jié)點(diǎn)的方式進(jìn)行去重。

ok，最后將前面的各種分析形成代碼。

其實(shí)就是bean，對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行封裝。
用到了lombok，挺好用的工具，感興趣的朋友自行研究下。

import lombok.Data;

/**
 * @description: 封裝節(jié)點(diǎn)數(shù)據(jù)
 * @author: liuzijian
 * @date: 2018-04-11 23:06
 */
@Data
public 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;
    }
}

用到了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<>();   //存儲(chǔ)圖
    Set existsNodes = new HashSet<>();  //節(jié)點(diǎn)去重
    LinkedList pathList = new LinkedList<>(); //FIFO隊(duì)列

    /**
     * 圖的初始化
     */
    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());
    }

    /**
     * 構(gòu)造塊中進(jìn)行圖的初始化工作
     */
    public ShortestPath(){
        initPic();
    }

    /**
     * 路徑查找方法的重載
     * 為調(diào)用方便，將參數(shù)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，之前總是對(duì)它一知半解的。最近兩天有幸拜讀公司大神同事，用Guava Cache作本地緩存的代碼，敬畏不已！遂決定潛心研究之并寫文章記錄，敬請(qǐng)期待。