美文网首页
图的BFS & DFS & Dijkstra算法

图的BFS & DFS & Dijkstra算法

作者: JaJIng | 来源:发表于2019-04-04 13:56 被阅读0次
    图.PNG

    python 队列实现的图的BFS,类似于哈夫曼树遍历:


    BFS.PNG

    栈实现的图的DFS:


    DFS.PNG

    BFS扩展最短路径:


    parent.PNG

    Dijkstra(加权最短路径计算):


    dijkstra 推导.PNG
    dijkstra.PNG 初始化.PNG
    Dijkstra.PNG

    写了个java版,比起js和python这种基于对象而不是oo语言,有点啰嗦:

    import java.util.*;
    
    /**
     * @author jajing
     */
    public class Dijkstra {
    
    
        private static class Node implements Comparable<Node>{
            String name;
            Integer distance;
            Node(String name,Integer distance){
                this.name = name;
                this.distance = distance;
            }
    
            @Override
            public int compareTo(Node o) {
                //正序
                return this.distance - o.distance;
            }
        }
    
        //图的两点间最短路径
        public static void main(String[] args) {
            Map<String,Map<String,Integer>> map = new HashMap<String,Map<String,Integer>>();
            Map mA = new HashMap();mA.put("B",5);mA.put("C",1);
            Map mB = new HashMap();mB.put("A",5);mB.put("C",2);mB.put("D",1);
            Map mC = new HashMap();mC.put("A",1);mC.put("B",2);mC.put("D",4);mC.put("E",8);
            Map mD = new HashMap();mD.put("B",1);mD.put("C",4);mD.put("E",3);mD.put("F",6);
            Map mE = new HashMap();mE.put("C",8);mE.put("D",3);
            Map mF = new HashMap();mF.put("D",6);
            map.put("A",mA);
            map.put("B",mB);
            map.put("C",mC);
            map.put("D",mD);
            map.put("E",mE);
            map.put("F",mF);
            Map<String,Integer>  result =  dijkstra(map,"A");
            for(Map.Entry<String,Integer> e:result.entrySet()){
                System.out.println(e.getKey() + ":" + e.getValue());
                /**
                 * A:0
                 * B:3
                 * C:1
                 * D:4
                 * E:7
                 * F:10
                 */
            }
    
        }
    
        public static Map<String,Integer> initDistance(Map<String,Map<String,Integer>> map,String start){
            Map<String,Integer> distance = new HashMap<String, Integer>();
            for(String key:map.keySet()){
                distance.put(key,Integer.MAX_VALUE);
            }
            return distance;
        }
    
        public static Map<String,Integer>  dijkstra(Map<String,Map<String,Integer>> map,String start){
            //最短距离表,初始都最大化
            Map<String,Integer> minDistance = initDistance(map,start);
            Set<String> seen = new HashSet<String>();
            //最短路径的父结点
            Map<String,String> parent = new HashMap<String, String>();
    
            PriorityQueue<Node> pQueue = new PriorityQueue<Node>();
    
            pQueue.offer(new Node(start,0));
            parent.put(start,"Null");
            minDistance.put(start,0);
    
            while(!pQueue.isEmpty()){
                Node current = pQueue.poll();
                //一定要在取出时才放到seen去!!
                seen.add(start);
                String currentName = current.name;
                Integer currentDist = current.distance;
                
                Map<String,Integer> connects = map.get(currentName);
                for(Map.Entry<String,Integer> entry : connects.entrySet()){
                    String nextKey = entry.getKey();
                    Integer nextValue = entry.getValue();
    
                    if(seen.contains(nextKey)) continue;
    
                    Integer newDistance = currentDist + nextValue;
                    if(newDistance < minDistance.get(nextKey)){
                        parent.put(nextKey,currentName);
                        minDistance.put(nextKey,newDistance);
                        pQueue.offer(new Node(nextKey,newDistance));
                    }
                }
            }
            return minDistance;
    
        }
    }
    
    

    这里要感谢@正月点灯笼的课件

    相关文章

      网友评论

          本文标题:图的BFS & DFS & Dijkstra算法

          本文链接:https://www.haomeiwen.com/subject/uvvfiqtx.html