Dijkstra计算最短路径

1.撸码

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @description: Dijkstra计算最短路径
 * @author: Liangyb (yunbo.liang@ucarinc.com)
 * @create: 2019/12/27 10:25
 */
class ShortDis {

    public static void main(String[] args){
        //起点
        String start = "A";
        //建立图
        HashMap<String, List<Node>> map = new HashMap<String, List<Node>>();
        map.put("A", Arrays.asList(new Node("B", 5), new Node("C", 1)));
        map.put("B", Arrays.asList(new Node("A", 5), new Node("C", 2),new Node("D",1)));
        map.put("C", Arrays.asList(new Node("A", 1), new Node("B", 2),new Node("D",4),new Node("E",8)));
        map.put("D", Arrays.asList(new Node("B", 1), new Node("C", 4),new Node("E",3),new Node("F",6)));
        map.put("E", Arrays.asList(new Node("D", 3), new Node("C", 8)));
        map.put("F", Arrays.asList(new Node("D", 6)));

        HashMap<String, Node> res = new HashMap<String, Node>();//存放起点到各点的最短路径
        PriorityQueue<Node> queue = new PriorityQueue<Node>();//优先队列，将去入队的节点按其dis字段从小到大的排列
        Node startNode = new Node(start, 0);//起点距离自身的距离为0
        queue.add(startNode);//将起点入队
        //BFS
        while (!queue.isEmpty()) {
            Node cur = queue.poll();//出队 出队的不一定是距离最短的
            if (!res.containsKey(cur.name)) {//添加进入res的一定是最短路径，如果出现重复添加，一定不是最短路径，故舍弃
                res.put(cur.name, cur);//将距离最短的路径添加进res
                List<Node> nodes = map.get(cur.name);//与该节点相邻的节点们
                //遍历
                for (Node node : nodes) {
                    if (res.containsKey(node.name)) continue;//不重复计算已经计算过的节点
                    queue.add(node.setDis(cur.dis).setParent(cur.name));//将没有计算过的入队
                }
            }
        }
        for (String s:res.keySet()) {//打印起点到各点距离
            Node node = res.get(s);
            System.out.println(node.name+":"+node.dis);
        }
    }

    static class Node implements Comparable<Node>{
        String parent;
        String name;
        int dis;

        public Node(String name, int dis) {
            this.name = name;
            this.dis = dis;
        }

        public Node setDis(int dis) {
            this.dis += dis;
            return this;
        }

        public Node setParent(String parent) {
            this.parent = parent;
            return this;
        }

        public int compareTo(Node o) {
            return o.dis>dis?-1:1;
        }
    }
}