【算】最短路徑問題

aervon 發布于2019-08-15 15:24 / 3201人閱讀

摘要：楔子最短路徑是很經典的一個問題，最初看到該類問題時毫無思路，而一旦抓到解題思路的主脈絡后，則會驚嘆于組織結構化數據的精巧問題是七個城鎮，它們之間的連線表示汽車行駛路線，而連線上的箭頭表示道路允許方向。

楔子

最短路徑是很經典的一個問題，最初看到該類問題時毫無思路，而一旦抓到解題思路的主脈絡后，則會驚嘆于組織結構化數據的精巧！

問題

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
 */
@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;
    }
}

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作本地緩存的代碼，敬畏不已！遂決定潛心研究之并寫文章記錄，敬請期待。

GPU云服務器云服務器最短路徑問題最短路徑問題算法最短路徑問題 c語言最短路徑

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69038.html

對狄克斯特拉算法的理解

摘要：致敬首先向偉大的牛人致敬使用狄克斯特拉算法如果所示找出從起點到終點耗時最短的路徑。狄克斯特拉算法思路步驟或思路如下找出最便宜的節點，即可在最短時間內前往的節點。狄克斯特拉算法是一種實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用。是貪心方法（greedy method）的一個成功范例。致敬首先向偉...

chuyao 2019-07-30 14:46 評論0 收藏0
【程序員必會十大算法】之弗洛伊德算法

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊學習資料迪杰斯特拉計算的是單源最...

JellyBool 2021-09-30 09:47 評論0 收藏0
王者編程大賽之五 — 最短路徑

摘要：由于是從頂點到的最短路徑，則有。算法流程根據最短路徑的最優子結構性質，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環首發于樊浩柏科學院自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具...

yuanzhanghu 2019-07-01 12:36 評論0 收藏0
【程序員必會十大算法】之迪杰斯特拉算法

摘要：推薦資料推薦學習文章代碼不能設置為否則兩個相加會溢出導致出現負權創建頂點和邊創建圖頂點數得到邊的數目調用算法計算最短路徑推薦資料推薦學習文章代碼 public...

番茄西紅柿 2021-09-29 09:35 評論0 收藏2637
【你該懂一點Javascript算法系列】之單源最短路徑 - Dijkstra算法

摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...

SoapEye 2019-08-23 15:04 評論0 收藏0