圖.PNG

python 隊(duì)列實(shí)現(xiàn)的圖的BFS闯睹，類似于哈夫曼樹遍歷:

BFS.PNG

棧實(shí)現(xiàn)的圖的DFS：

DFS.PNG

BFS擴(kuò)展最短路徑：

parent.PNG

Dijkstra（加權(quán)最短路徑計算）：

dijkstra 推導(dǎo).PNG

dijkstra.PNG

初始化.PNG

Dijkstra.PNG

寫了個java版休玩，比起js和python這種基于對象而不是oo語言，有點(diǎn)啰嗦：

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;
        }
    }

    //圖的兩點(diǎn)間最短路徑
    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>();
        //最短路徑的父結(jié)點(diǎn)
        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;

    }
}

這里要感謝@正月點(diǎn)燈籠的課件