使用广度优先搜索，计算路径最短问题

佚名 5年前 (2019-07-27) 算法 1258人围观抢沙发百度已收录

问题，求出任意两个站点间的最短距离

广度优先搜索可解决的问题

从A节点能否到达B节点
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
从A节点到达B节点的最短路径

广度优先搜索的原理

先搜索A节点的所有子节点，过没有找到结果，再从每个子节点的字节点搜索。如此反复。

注意：必须按顺序从所有一级节点开始搜索，再从二级节点，三级节点，以此类推。

参考原理图

代码实现

对站点建模

 static{
        //对站点建模
        map = new HashMap<>();
        map.put("A",new String[]{"B","D"});
        map.put("B",new String[]{"A","F"});
        map.put("C",new String[]{"E","G"});
        map.put("D",new String[]{"A","G"});
        map.put("E",new String[]{"C","I"});
        map.put("F",new String[]{"B","H"});
        map.put("G",new String[]{"C","D","I"});
        map.put("H",new String[]{"F","K"});
        map.put("I",new String[]{"E","K"});
        map.put("J",new String[]{"K"});
        map.put("K",new String[]{"J","H","I","N"});
        map.put("N",new String[]{});
    }

因为是任意两个相邻站点都可以来回，所以每个站点都是相互的子节点。

如果有单向的站点，建模时，只设置成一方的子节点。

代码

public static void shortestWay(Map<String,String[]> map,String start,String end){
        Queue<String> queue = new ArrayDeque();
        //将起始元素的所有子元素加入队列
        addStringArr(queue,start);
        //最短路径可能有多个，设置一个标志，记录最短路径的长度    
        int i = 0;
        while(true) {
            //每次从队列弹出队首的元素
            String s = queue.poll();
            //比较字符串最后一个字符
            if (end.equals(String.valueOf(s.charAt(s.length()-1)))) {
                if(i == 0) i = s.length();  // 第一次找到最短路径，记录长度
                if(s.length > i) return ;   //长度大于最短路径长度时，结束
                System.out.println(start+"节点到"+end+"节点的最短路径是："+s);
            } else {
                //结果不匹配，把该元素的所有子元素加到队尾
                addStringArr(queue, s);
            }
        }

    }
    // 将元素s的所有相邻元素加入队列尾部
    public static void addStringArr(Queue<String> queue,String s ){
        //每次取字符串最后一个字符
        for (String str  : map.get(String.valueOf(s.charAt(s.length()-1))) ){
            //每次把子元素加入尾部时，在字符串前面拼接自己。
            str = s+str;
            queue.add(str);
        }
    }

为了在结果中显示出最短路径。如A节点到I节点的最短路径时：ADGI

每次将子元素加入队列尾部时，在子元素字符串前面加上父元素字符串。

在比较结果时，取元素的最后一个字符比较。