【算】最短路径问题

aervon 发布于2019-08-15 15:24 / 2985人阅读

摘要：楔子最短路径是很经典的一个问题，最初看到该类问题时毫无思路，而一旦抓到解题思路的主脉络后，则会惊叹于组织结构化数据的精巧问题是七个城镇，它们之间的连线表示汽车行驶路线，而连线上的箭头表示道路允许方向。

楔子

最短路径是很经典的一个问题，最初看到该类问题时毫无思路，而一旦抓到解题思路的主脉络后，则会惊叹于组织结构化数据的精巧！

问题

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作本地缓存的代码，敬畏不已！遂决定潜心研究之并写文章记录，敬请期待。

海外云主机私有云最短路径问题最短路径问题算法最短路径问题 c语言最短路径

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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