两点间最短距离 - Dijkstra

一、汇总

Dijkstra

二、Dijkstra 原理

借助java工具类：PriorityQueue 默认内部元素强制根据指定规则进行自然排序的的小顶堆，每次选择下层节点到起点开始算的最小权值的节点作为当前节点，进行向外的下一个层级的探索，最终让所有节点都保存了，此节点从开始节点的最小权重值及其最短路径的父节点。

三、Dijkstra 代码实现-Java版本

有必要讲解一下代码结构：

1. 内部类的使用
   1. 体现更强的封装性，结构体仅供外部类使用，不对外暴露。
   2. 外部类可以直接调用内部类，简化代码。
   3. 内部类也可以直接使用外部类的成员变量，此例子中暂无体现。
2. 优先级队列的使用
   1. 比较器的构造。
   2. 因为每次向外层探索时候，都会加入下一层到开始节点权重总和最小的节点，此数据结构强制进行排序，序列化为一个小顶堆。这也是提升此算法性能的关键设计。
   3. 默认为小顶堆。
   4. 距离Map和路径反向记录Map，都体现了算法设计的技巧。
   5. 尤其在打印路径时候，最终用递归思想。

package algo.backtrace.Dijkstra.weiwei;

import java.util.*;

public class Dijkstra {

    class Grap {

        // 带权重的无向图表示，邻接矩阵表示
        Map<Integer, List<Edag>> adjList;

        Grap() {
            adjList = new HashMap<>();
        }

        // 添加边
        public void addEdag(int start, int des, int weight) {
            adjList.putIfAbsent(start, new ArrayList<>());
            adjList.putIfAbsent(des, new ArrayList<>());
            adjList.get(start).add(new Edag(des, weight));
            adjList.get(des).add(new Edag(start, weight));
        }

        // 获取一个顶点的所有边
        public List<Edag> getEdags(int node) {
            return adjList.getOrDefault(node, new ArrayList<>());
        }

        // 获取所有顶点
        public Set<Integer> getAllNodes() {
            return adjList.keySet();
        }
    }

    // 描述边
    class Edag{
        int des;
        int weight;
        Edag(int des, int weight) {
            this.des = des;
            this.weight = weight;
        }
    }

    public Map<Integer, Integer> dijkstra(Grap grap, Integer start) {
        // 定义工具
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
        Map<Integer, Integer> dist = new HashMap<>();
        Map<Integer, Integer> prev = new HashMap<>();

        // 初始化参数
        for (Integer node : grap.getAllNodes()) {
            dist.put(node, Integer.MAX_VALUE);
            prev.put(node, -1);
        }

        dist.put(start, 0);
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            int currNode = poll[0];
            int currWeight = poll[1];

            if (currWeight > dist.get(currNode)) {
                continue;
            }

            for (Edag edag : grap.getEdags(currNode)) {
                int newDist = currWeight + edag.weight;
                if (newDist < dist.get(edag.des)) {
                    dist.put(edag.des, newDist);
                    prev.put(edag.des, currNode);
                    pq.offer(new int[]{edag.des, newDist});
                }
            }
        }

        System.out.println("dist:" + dist);
        System.out.println("prev:" + prev);

        return prev;
    }

    public void printTrace(Map<Integer, Integer> prevMap, int traget, List<Integer> trace) {
        if (prevMap.get(traget) == -1) {
            return;
        }

        traget = prevMap.get(traget);
        printTrace(prevMap, traget, trace);
        trace.add(traget);
    }

    public void main(String[] args) {
        Grap grap = new Grap();
        grap.addEdag(0,1,4);
        grap.addEdag(0,2,1);
        grap.addEdag(1,3,2);
        grap.addEdag(2,3,8);
        grap.addEdag(2,4,3);
        grap.addEdag(4,5,2);
        grap.addEdag(3,5,1);

        Dijkstra dijkstra = new Dijkstra();
        Map<Integer, Integer> prevMap = dijkstra.dijkstra(grap, 0);
        List<Integer> list = new ArrayList<>();
        dijkstra.printTrace(prevMap, 5, list);
        System.out.println(list);
    }
}


// 输出
// dist:{0=0, 1=4, 2=1, 3=6, 4=4, 5=6}
// prev:{0=-1, 1=0, 2=0, 3=1, 4=2, 5=4}
// [0, 2, 4] 瑕疵之处是traget 没有打印出，无伤大雅。